|What exactly happens when you try to start in safemode?|
"that doesnt go anywhere." is not an accurate description.
Do you get the same kind of error message? Logging into safemode requires use of the Admin account password. Do you know it? It may be blank.
There are millions of hits on google for this type error and it may be either hardware or software related. Since you know your system has been compromised by one of those antivirus nags there is a good chance yours is a software problem. If you can get into safemode I suggest you should turn off system restore. This will delete all previous restore points but they were likely to have been infected anyway.
Then see if you can run antivirus and other malware scans.
Goin' Fishin' (Some day)