Awww, what a bad bug.
Do they still work? (like, run the application).
This usually happens if the directory of the app changes (very rare). Or the drive letter changes, from C to E.
Tip: Delete all of the START icons, right click on the working icon, click ADD TO START MENU. Deleting them all, should make them reset and the list should start filling up as you use the applications.