Signs of getting compromised
 

Today any web browser I use has randomly been brining me to http://www.xn--51haaaaaaa.com/ at random intervals.

I've run chkrootkit from a live cd, and rkhunter, clamav, f-prot, and bitdefender, nothing's unusual.

All the definitions were up to date.

I'm wondering if its possible that my router got hacked. I'm not sure this is even possible, but it's acting weird. Tried reflashing its firmware, didn't fix it.

I'm totally clueless...

that sever has some nice ports open:
PORT STATE SERVICE
21/tcp open ftp
23/tcp open telnet
25/tcp open smtp
80/tcp open http
110/tcp open pop3
135/tcp filtered msrpc
139/tcp filtered netbios-ssn
445/tcp filtered microsoft-ds
593/tcp filtered http-rpc-epmap
1720/tcp filtered H.323/Q.931

THe interesting port open from that site you gave is the tcp 593 port...that's for CIS which is for tunnelling...get your ip addy and use nmap and see what you've got open on your side...might give you clues on what to look for

How "randomly". Describe it more clear, please, and which browsers you use. What URLs are you trying to visit, is there an URL which causes that all the time?
To be sure about router, scan it's ports from outside, if possible.
You can also try using different DNS server, say, google's ones.
2 MrChilly0: you see 135,139,445 etc as filtered. Probably they are blocked by your ISP(it's a common case), most ISPs block outgoing packets to those ports.
--upd:
www.xn--51haaaaaaa.com not resolving here.

Problem seems to have gone away. I nmap'd myself, nothing odd running, and nmap'd the router, nothing odd either.

Problem seems to have gone away.

Firefox, Epiphany, & Iceweasel all did it.

I got a good chuckle out of the port scan results from that server though...

You know it can be back again, what would you do in that case?
From here it looks like DNS cache been poisoned but it's a guess. So you may wish to try using different DNS servers in case that will happen again. Say, google's ones, or local. I suppose you use your ISPs DNS. I personally use the one I run on the router and since I moved to it, I also have no troubles with regular work, our ISP's DNS is quite buggy, and perhaps our ISP is not the only one having this problem.
BTW, Iceweasel==Firefox if you didn't know ;)

Now using OpenDNS and its still gone. AT&T DNS fails apparently.

I have whatever version of Iceweasel is current in Lenny, and Firefox 3.6 manually installed.