Thanks, guys. I went in and switched the icon to something else, then switched it back, and it was a success. Just reapplying the same icon wasn't doing it.
The shortcut was launching the program just fine, Oli, just not the icon.
So odd that was happening just in the All Programs folder. Does it have a separate icon cache?