I am suddenly having more or less the same problem, but only with one shortcut (iTunes).
It all used to work perfectly, then something went haywire with just that shortcut.
I have all of my music and videos in a shortcut folder named "Entertainment".
I deleted the old iTunes shortcut because I kept getting a "File not found" error when I clicked on it in that stack.
I created a new shortcut for iTunes on my desktop, tested it (it worked), opened the Entertainment folder, moved the shortcut into that folder, tested it (it worked), closed the folder, checked the Entertainment stack, the new shortcut was in there, clicked on it ... and "File not found."
I could see this happening if something was wrong with the bloody shortcut, but if I open the folder (even through the Stack Docklet) and click on the shortcut, it comes up just fine. All of the other shortcuts in that (and every other shortcut folder) work perfectly.
I'm on a Windows 7 64bit system, but I wouldn't think that would make a difference for one single solitary shortcut.
Any thoughts??