VS2005 Deployment Project, Deploy To everyone glitch

I have a VB.NET Project,
I added a Set-up Project to the original.
Added Shortcuts to Desktop and Program Menu
Selected install to everone on the PC.

The installation works fine.
The application and shortcuts work.

If you go to another user on the PC all appears fine, but if you click the short cut on the desktop or user program menu it does not run and appears to be looking for the set-up .msi file.

I can go to Program file\AppFolder\ click the App's.exe file and it runs ok.

The shortcuts fail, what did I foul-up?
Any help would be appreciated.

CD