Virus Causes Desktop to Vanish

My computer is currently infected with what seems to be a fairly bad virus.
Initially, the only problem that occurred was simply an inconvenience (and only presumably related to the virus): Upon clicking on a link brought up by a Google search, instead of being directed to that page, I would be directed to a seemingly random search page (one of those that have links to various sites that supposedly are related to what you searched for).

However, the real problems started when I tried to access Control Panel/My Computer or right clicked on the Desktop. (After the Control Panel instance, I did a system restore, hence knowing that the others caused the same problem.)

When I did either of those things, the desktop and start menu bar both suddenly disappeared (leaving only my background image). I could still access the Task Manager, but attempting to run any virus programs causes them to be uninstalled.

Is there anything I can do to solve this problem? I am unable to restore my system any further, so I need another solution.

On another note, I'm fairly certain what caused the virus in the first place: when attempting to watch a streamed video, I was asked to install the latest upgrade to flash...which, I did. That is to say, I installed the program which popped up following this message.

Please do not bother commenting on my idiocy. Believe me, I already know.