Just to update: I ran Avira anti-vir and Lavasoft AdAware. Avira found 7 trojans and some spyware, AdAware found a few too. All of it cleaned, system restarted, started up Firefox, went to Google typed in a search question and *bam* same error message.
So I logged into my router to see if there are unsolicited packets going in and out of my network, and it was all clear. Everything that was departing and returning was fully authorized, and I examined the packet logs myself, but nothing out of the ordinary. I don't know what is going on.