I've had the same problem and although I don't know how to solve it yet, I do believe I know what causes it.
It is not malware- ran a scan, no problems. Nor is it a byproduct of a recent Windows update as I have thought. I also noticed the same thing happening with a Canon printing software program I installed at the same time.
This is a security problem- essentially, Windows is not letting you & I have access to the program in order to run it. I went to the Program files folder, clicked on the Canon folders, and was able to change the security settings to allow me to use it and run, and voila- my shortcuts now work. I tried the same steps with Windows 7 Upgrade Advisor and although I was able to get into the folder, it is still not letting me run the program.
Now, instead of the shortcut error, I am getting this error-Windows cannot access the specified device, path, or file. You may not have the sufficient permissions to use this file.
I fully admit that I am wandering in the dark with this, and wonder if anyone can lead me in the right direction as to what to do.