1. Windows Firewall: try to disable it.
2. Router, if any: check the configuration, although it's unlikely for a router's settings to be reset with a format.
3. Update Windows: install the latest service pack.
4. Check how your internet configuration is installed on the computer, in case there is no router and you have to install something before connecting to the internet.
Can't think of anything else at the moment, but I might dig into the topic.