Danger - don't use Tweak UI's "rebuild icons"
When I reinstall XP (which I do too often) I always round up my customizations (which I can do in under 10 minutes blindfolded... sigh) with a bunch of tweaks inside of Tweak UI. Normally I never fuss with that "Repair" area, but for some odd reason I decided to click "Rebuild Icons" this time around. It didn't appear to do anything at first until I connected to my machine via Remote Desktop (which is how I connect to most of my machines...)
It had somehow messed up and all my icons in the taskbar, "Save As..." dialogs, desktop, etc. were all in 16 bit color. I even tried installing XP SP3 RC to see if it helped. I followed numerous suggestions about "tricking" Windows into re-caching the icons, deleting the icon cache, etc. Nothing fixed it. Finally, I came across a forum post (well, actually it was the first result in Google but this particular suggestion was the last one I tried) that had the magic fix. It's a simple .reg file that resets some icon settings somewhere. It was the only thing that seemed to do the trick, and I have decided to host a copy of it just in case that link ever goes dead. So, thank you to "wissnx01" at That Computer Guy's forums.
To fix the issue, download this zip file and merge the .reg file inside of it. Reboot (or maybe even just logout and log back in) and voila. Fixed.