I tried changing the icons next to the list of programs in the start menu and still nothing.
I rebuilt the cache, I clicked apply...but nada...anyone got any ideas what's going on here?

maybe you should click "Apply" just after you choosed the custom icons, 'cause Iconworkshop doesn't change the icons in the right time you choosed what icon you wanted to use, you must "Apply" the changes. Maybe it would help you. What version are you using? Are you using Iconworkshop?

Yep, clicking apply and then rebuild cache.
Always did.
Version 6.01
The icons I want to change are the ones right in front of the programs listed under start-programs.
But I noticed that the icon only changed for programs in the subfolders, listed there.