Well personally I would start by adding the above to allow the local network to communicate.
It might be a good idea to start from scratch with the firewall, ie: reset all settings. That way, you can ensure that all necessary files and programs are permitted - you may have something blocked that shouldn't be.
You may get requests from files such as
SVCHOST which is often necessary for Internet to work over a shared connection.
Also, make sure, in
Internet Connection Sharing, that
Allow other network users to connect through this computer's Internet connection is enabled.
Have a read of this too, it may help:
How to configure Internet Connection Sharing in Windows XP
