Goto a console and type cat /etc/resolv.conf and post the results.

You mention that Konqeror "seems to work fine" is Konq 100% and this just effects other browsers? Or can you reproduce it in Konq? With the EXACT same results.