Why do I get redirected to a weird Chinese site for non-existent websites?
This can be caused by a few things:
A DNS server is injecting false responses (try setting your DNS to 8.8.8.8, Google's server)
A proxy at your ISP (that'd be quite weird, almost malicious)
Your router injecting false DNS responses
That's all I can think of now. I would bet it's not caused by any Ubuntu software.
You can check your DNS provider's integrity by typing this into a Terminal:
dig siadfiosjdfosjdfsifjs.co.nz | grep ANSWER
The result should say ANSWER: 0.
OpenDNS does something similar for their free service (redirect to an ad page). Since it works with any "bad" address, its most likely a DNS redirect on your providers side. Its a pretty sleazy thing to do (sell advertisement space for bad address requests) but not unheard of. Check /etc/resolv.conf to make sure someone hasn't hijacked your computer by changing your dns settings however.
If your resolv.conf points to your official ISP DNS server or to your router then to double check that your ISP is indeed responsible to do so - open /etc/resolv.conf in your favorite text editor (under sudo because its a system file) comment out the lines in the file (comment out with a hash #) and type in nameserver 4.2.2.1 which is a known good top layer dns server.
If that doesn't fix the issue - do other computers on the same network exhibit the same problem?
EDIT
Based on your comment it seems that your resolv.conf was modified - this line in particular
search 520b.com
which goes to a suspiciously similar website to the one in your OP.
There are two distinct possibilities here - either your computer was compromised or your router. I would check your router settings to see if someone has modified the dns settings on it, since your computer (most likely) obtains dns/routing information automagically via dhcp any bad configuration on the router side will propogate to your computer. There is also a remote possibility of ISP mischief - who is your ISP?
Since DHCP clears resolv.conf every time it obtains a new address there is little chance that your PC is compromised if you are using DHCP (As it would reset every reboot at least and assuming that your router is clean), if - however- you are using a static configuration someone/something may hae altered your resolv.conf file in the past and it has stayed there since.
My ISP is TalkTalk. I was using the default setup of my router and connecting to it wirelessly using automatic DHCP. This was what my router configuration and my connection looked like (router config page is at http://192.168.1.1/):
So my computer used the DNS of 192.168.1.1 which used the router DNS of 62.24.243.1 (primary) and 62.24.243.2 (secondary). This redirected me to a page that seems to be from 520b.com (not linking directly because I don't want to reward them!).
When I changed the DNS for my computer to 8.8.8.8 and rebooted, this problem disappeared and instead I got the expected result of my web browser telling me it couldn't find the page.
I wanted to test if my router had been modified to cause this so I used the router configuration to reboot the router to factory settings. I also set my computer to use the router DNS again. After this, the problem was present again. The factory settings for the router use 62.24.243.1 (primary) and 62.24.243.2 (secondary) for DNS. Therefore, the problem was the default DNS that TalkTalk uses.
This is certainly dodgy but it could be that TalkTalk doesn't own the DNS and they themselves are being screwed. Either that or TalkTalk is evil.
Anyway, my long term solution is to set the router to use Google's DNS (8.8.8.8 primary and 8.8.4.4 secondary). I can get to this by clicking 'Advanced', clicking ok on a patronising dialog:
and navigating to Basic->DHCP. I then entered the IP addresses into the correct boxes then clicked a submit button. After this I rebooted my router and computer and everything was fine.