Firefox 3.5.7 slow DNS resolution on windows

Recently I've had a problem with firefox. It would take up to 10 seconds for each DNS request making browsing to any site extremely slow.

I tried clearing caches, changing settings in about:config but nothing worked.

The only thing that worked was to create a new default profile for Firefox and copy all the bookmarks, extenstions, etc over to the new one.