Hello BeachNut, and welcome to Seven Forums.
It doesn't seem to work that way for me either.
Here's a workaround though. Create the folder on the desktop first, then change it's icon. Afterwards, move (drag and drop) the folder to the Start Menu All Programs
location for current or all users instead. It will then show up in the All Programs area with the new icon.
Hope this helps,