I have the same virus that the OP posted. This is a new virus and is not the same as the one referenced in the above link. I have access to the internet in safe mode. The virus went away for a few hours, but it came back. I haven't been able to get rid of the virus using Malwarebyte's, Super Antispyware, along with several other programs.
Malware Protection is itself the virus - it's a type of infection known as a rogue Programme as it pretends to be a real anti spyware/virus programme to scare you into purchasing it.
If you do have malware protection, have a look at the removal guide for it here:
If it is that particular rogue, follow the instructions if you can and see if that helps to clear it. If that doesn't work, post again to get more expert help!
EDIT: Good news, I have rid the virus from my wife's desktop. The virus is still on mine so I hope to resolve it soon.
Edited by hamluis, 28 May 2011 - 10:50 AM.
Split from different topic, PM sent new OP.