Why didn't I think of that?!?!
It's just not as intuitive as say WinXP... I'm still getting used to there being no properties menu in the click-and-hold popup menu.
I did as you said, erased the old shortcut. Then copied the new program .EXE target and did a "Paste Shortcut" in \\Windows\Start Menu\Programs\. Fixed everything!
WM5 is really starting to come around for me (thanks to aximsite.com, not the developers!)