I have just installed Ubuntu 12.10 and when I attempt to search Google I receive the following error message:
We're sorry...
... but your computer or network may be sending automated queries. To protect our users, we can't process your request right now.
This can happen when a lot of people share the same external IP. For example, behind campus networks and the like.
If this sounds like your situation, then either try waiting a while for the IP to (hopefully) be removed from the blacklist, or use a proxy to access the website.
If this doesn't sound like it, i.e. you're using a small home network, then you can try obtaining a new IP address (assuming you have a dynamic IP account with your ISP) by powering down and powering back up your modem - whether it's Cable, ADSL or otherwise.
If you're concerned about malware (very unlikely - both because it's uncommon on Linux, and also because it's extremely unlikely any malware would choose to repeatedly hit Google's search page), then you might choose to use a tool like Wireshark to monitor outgoing packets. Or, even better, run Wireshark on another PC on your home network using promiscuous mode. However, like I say, that's extremely likely to be a waste of your time.
Many ISPs place you behind a transparent web proxy these days.
This has advantages for them (lower interconnect fees) and for you (lower latency and less clogged pipes) but it aggregates all requests for that ISP as if they came from one IP address.
You may have fallen foul of the activities of other machines on your ISP network. As a commenter says, malware is uncommon on Linux, although not impossible.
