Do you use kppp for dailup connections, or another program (e.g if you have DSL or Cable)?
When using kppp, check if the dns servers of your providers are configured correctly.
When using another type of connection, open /etc/resolv.conf as root with an editor, like kwrite.
Place your nameservers in this file, like this:
nameserver 123.456.789
nameserver 234.567.890
Rinse