Tu n'aurais pas un proxy invalide qui ferait que la connexion ne se ferait pas ?
Ou alors, avec la nouvelle connexion Free, tu n'as pas les bon serveurs DNS. Une fois connecte, essaye dans un cmd.exe de faire:
C:\> nslookup www.google.fr
Sinon, dans les option avancees IE, decoche "Montrer des messages HTTP amicaux" (Traduction a peu pres de ce que j'ai moi: "Show friendly HTTP messages" ) pour savoir quel est le probleme exact.