Another success story here: Trojan Remover was the solution to my nightmare. I was fixing a relative's PC that was exhibiting all the symptoms mentioned here: Browser search results redirected, Anti-virus/anti-malware websites blocked, unable to update AVG or any other program, unable to Install any other anti-malware programs, unable to change desktop wallpaper.
Nothing worked, AVG, Spybot, Avira, even PE level virus scans. I was ready for a re-install until I found this forum, and all your suggestions worked! Trojan Remover got rid of the nastiness so I was able to update everything else, run scans, install other progs, runs more scans, and now this PC is back to its old self again. Thanks all!