Okay, we've been tackling this one a good bit here lately. While FP is right in that the only true way to make sure you're clean is to do a complete reinstall, fear not, because you can defeat this.
We've been hitting it with a combination of TDSS Rootkit Killer, Combofix, Hitman Pro, Microsoft Security Essentials, Malwarebytes, and SuperAntiSpyware. We've had a great amount of success with this thus far. Yeah, it's a lot of work to put into it and a reinstall would probably be easier, but some of our clients aren't too keen on reinstalls, unfortunately.
Those programs above should be able to nuke nearly every infection on the PC without much issue. To take care of the hidden files, Grinler (BleepingComputer) created a small utility that unhides the hidden files and folders, but is designed (afiak) to not unhide files that are supposed to stay hidden. You can find that here:
http://www.technibble.com/forums/showthread.php?t=26127
Now for the last part, the All Programs menu. If you have Windows XP, you're pretty much on your own, unfortunately. Microsoft's TweakUI tool will help get your icons back in order (Use the Icon Repair option) and then you'll have to manually go into Program Files and create new shortcuts for the EXEs.
Vista and 7 users have it easy. If you navigate to %programdata%/Microsoft/Windows, right click on the Start Menu folder, and hit Restore Previous Versions, you can go back a few days to where the icons were still in tact, and restore them from the Previous Versions.
Now I have to stress again, I completely agree with Flying Penguin. Backup backup backup, reinstall. It's the only 100% safe way to make sure your PC isn't rootkit'd or keylogger'd. But we've been using this method and it's given us great results.
Best of luck, and happy virus hunting!