Did the scans pick up anything, but just couldn't remove it, or did they not pick up the threat at all? If you want to rid yourself of the it, and the usual removal software isn't doing the trick, then you'll need to figure out the name of the threat and do some research on it's particular removal. If you can't figure out the name, then you can try searching on the files and/or processes it uses. If you don't know that either, then search on some of the text that appears in the pop-up window.
Chances are that other people have had the same threat and have already rid themselves of it. Often times there are specific tools designed to remove particular threats, so look for those as well. Just remember to run checks on ANYTHING you download. If all else fails, there is always manual removal, but you'll need a good understanding of malware and computers to do that. Anyway, just let me know your progress and I'll do my best to help.
There's a free program called
HiJackThis that can be really helpful in tracking down hard to clean threats. If you run a scan and copy/paste the text into a post here, then I may be able to track down a possible solution for you...