There are several ways to do this, but I think mrgreek's way is probably the least confusing one. (The fastest way is simply updating the existing screwed-up shortcuts, but if you are not comfortable searching and navigating through Windows it may be easy to get lost)
Remember if you create a whole new set of desktop icons, you need to delete the old ones.
In fact you don't need to create the shortcuts in the folder of the program then drag and drop it to desktop - right click on the icon of the program .exe (executable) file -> Send to -> Desktop (create shortcut)
You also need to know what the .exe files for each program are, and sometime it is not obvious as firefox.exe (eg. MS Word is WINWORD.exe). I dont have an ideal way to find them, but if you had all those programs installed before the desktop shortcuts are screwed up, you can find the names of the .exe files for each program by doing the following:
Right-click on the faulty desktop shortbut -> Properties -> it will show you the path of the shortcut leading to the .exe itself. Note the name of the .exe as well as the path (eg. C:\program files\microsoft office\office12\WINWORD.EXE). When you use Windows Explorer (or "Computer") to get into list view (click one of the little icons in the top right corner of the window frame (I think it is the one closest to the left) to select "list") of your computer, you should be able to trace down the tree to find the .exe file so that you can create a desktop shortcut.
If the shortcut link is screwed up, at least you know the name of the .exe file and the general locale (eg. WINWORD.exe can be found in a folder under something like "microsoft office"), which is going to help in your search.
If your faulty desktop shortcuts are really screwed up, another place you can try the relevant information is Start -> All programs, where you can find the access to the folders and various program files. You can do the same thing by right-clicking on the name of the program -> Properties to see the path of the shortcut link.
Hope this helps.