Why on earth would anyone pay Best Buy to "clean" their system if they are already talking about reformatting the damn thing? You can reformat on your own, for free, without having to pay Best Buy, Geek Squad, etc.
The only time that a reformat is fully recommended is when the malware in question is a backdoor bot. Otherwise I suggest you download, and install Malwarebytes' AntiMalware.
http://www.malwarebytes.org/
Once installed update it and run a quick scan. Once finished reboot like it will prompt you to do so.
Since you say you have to start up in Safe Mode you'll be doing this through Safe Mode. Hopefully that will fix your problem.
================================================================================
If whatever malware you have isn't letting you install Malwarebytes then do the following.
Download Malwarebytes and rename "mbam.exe" to "mbam.com" then install it. Afterward go into the program file folder and find "mbam.exe". it's location should look something like this
"C:\Program Files\Malwarebytes' Anti-Malware"
Change that to "mbam.com" as well then update, run quick scan, and reboot when prompted.
When malware is removed go back and change everything you changed back to the way it's supposed to be.
==============================================================================
If you insist on starting from scratch then look into reformatting your system yourself. Assuming that you're still on Windows XP like the majority of the internet then head over to this article.
http://helpdesk.its.uiowa.edu/windows/instructions/reformat.htm
If you take this option, completely ignore everything involving Malwarebytes' AntiMalware.