I knew I shouldn't install 2 AVs, but I was desperate and they didn't seem to conflict. Regardless, I uninstalled Avast.

I was able to install MalWareBytes, but it would not execute. When I click it, the hourglass appears for a few seconds then disappears.

I rebooted and tried SuperAntiSpyware again and this time it ran. It found 9 registry items, all related to RootKit and I was able to remove them.
MalWareBytes still didn't work and the issue exists with SpyBot as well (won't execute).

I was able to execute Ad-Aware and download the current definitions now.

If I can't resolve this thing today, I'm going to throw in the towel and do a Ghost Image restore from when I first built it. (I'll back up his data first, but I know he's installed and configured a number of items that he'll lose. I've already prepared him for this and he's Ok with it, but it bothers me that the problem was not resolved).