Being able to browse in Firefox through one router but not another, and then being able to browse with Konqueror when you can't (or only very slowly) with Firefox is indicative of an IPv6 problem. Absolutely 150% sure!
To prove this, disable IPv6 in Firefox. Type 'about
:config' in the address bar (without the quotes). Then 'ipv6' (again no quotes) in the filter. You'll see a line beginning 'network.dns.disableIPv6...' Double (or right) click on 'false' to change it to 'true'. Close Firefox and open it again. Now you can browse OK, can't you? And addresses resolve promptly don't they?
This problem is often caused by older firmware in routers that cannot handle IPv6 modified IPv4 addresses. So if you get a replacement router of the same make and model you may still have the same problem - unless you are lucky enough to get one with later (and improved) firmware. If all else fails try searching this forum for disabling IPv6 system-wide. You have to edit a couple of lines in a system file, but I can't remember the details at the moment. You need a system-wide fix, rather than just disabling IPv6 in Firefox, because the yum-based utilities will probably be affected as well. They certainly were in FC3 and FC4 when I was plagued by this issue. I don't know about FC5, but I'm sure it's still so.