Windows 7 icons and programs missing

The customer has a Win7 Pro system.  He called in saying that his icons and programs were gone, and he was getting a bunch of crazy errors on the screen and a scan running that looked like one of those bogus scana programs that often infect systems.

I am on-site now, and the only icon I see is recycle bin, and if I go to Start> All Programs, there is nothing on the list.  Also, there is no icon for 'Computer', but if I type 'Computer' in the search box, it shows me the drives, but no files or folders are visible.  Note that if I go to the search box and type in a few letters of the content of some of his Word docs, for example, and click on it, it comes up just fine in Word.  It's as if everything is there, but I can't see it.  Same with his emails that I can search on in the search box.

I booted up in safe mode with networking and installed/updated spybot and malwarebytes, and while they found about a dozen trojans and other bad stuff, cleaning those did not solve my problem.  I have tried to restore multiple restore points, but each time it comes back and says it cannot do it becuase the restore point is damaged or missing.  I have run spinrite, but it found no physical problems on the drive.

I am thinking about removing his drive and connecting it to a different computer, to see if I can save his files, and then reformat his computer and reload Win7, etc.  But I obviously don't want to do all that to him if there is an easier fix.

Has anyone seen this problem in the past and has an easy fix?  TIA