Just a quick update, I'm still trying things, and a reboot into Windows 98 worked fine, full color icons, etc., so I can at least rule out a hardware problem for sure, its something to do with Win 2000.

I logged on (to win 2000) as a different user, and the same thing, bad color icons, games won't work.

At least its getting narrowed down, but I'm pretty much out of ideas. What else can I try?