If your router is configured to be a dhcp server. You would just type in 'dhcpcd' or whatever the mandrake dhcp client alias is and it automatically uses your router's configured dhcp settings. That might be your problem.
My suggestion is to nslookup google.com, ping the domain than ping the address compare the times. If the domain takes a long time to resolve you problem is with your dns server configuration. You are not required to use your ISP's domain servers (especially if they are slow and sucky;)).
To modify your nameserver 'vi /etc/resolv.conf'(or nano or pico or whatever your favorite editor is)
#To use this file just add entries in this format:
# nameserver address
#You can also add static entries with:
# domain address
Um your going to have to do some research to get a list of higher level dns servers to bypass your ISPs. Compare your DNS server in windows to the default one used on linux. I really don't think traceroute or tracepath will help since it doesn't seem to be a routing problem, unless you're supposed to be using a proxy server of some type, but usually that would make things slower if you have a broadband connection.