Tech Advice Needed - Malware Problem

[DarkHyren]

Can I run this in conjuction with my other anti-virus s/w?

You can, but I wouldn't recommend it.
You should only run one anti-virus on your system as they dont play nice with each other.

Also, (noob question here) should I run it in 'safe mode'?

If your system has been breached then running scans, system restores and such from safe mode is often your best bet as safe mode limits file and registry access (less chance of the virus spreading).

I guess I just want to make sure they are removed altogether avoiding having to do a complete re-install.

I would say get SpyBotSD and run it a few times to check the registry for nastys.
That program coupled with your anti-virus and windows user account control (which is on by default) should protect you.