New
#11
If I'm not mistaken, if you change the icon for an item, the new icon appears everywhere in the system, wherever the old icon used to appear. For example, if you change the icon for a program on the Desktop, the new icon for that program would appear in the Start Menu, if you pinned it to the Start Menu, or in Windows Explorer if you looked for the program's folder there. So rather than trying to go into the Start Menu (as you are) to change an app's icon, why not just change it from the Desktop or some other easier location. The change should apply to it's location in the Start Menu when you're done.
Here are a few interesting tutorials that might help (one of which was written by Arc!):
Folder Icon Change
User Folders - Change Default Icon
How to Change Windows 7 System Icons Using Resource Hacker
Windows 7 Tray Icons Changer by =Kishan-Bagaria on deviantART