fdisk it from linux, Its the only way to be sure. :)
Seriously though, the only way to fix stuff like that is to get outside the system. Boot with a livecd like knoppix and run a virus scanner on the infected partition.
There's usually no way for an infected system to "heal thyself" without an uninfected reference point to work from. If you have to boot into the compromised OS to try to fix it, the malware gets the first move.
