[Solution] All your .LNK are belong to Firefox
Stupid problem #107: The great Firefox (insert application of your choice here) take over. Symptoms include all links suddenly becomming assosiated with an errant application (thanks Firefox) and no longer working as links. This is thankfully a per profile thing with limited users but fixing it involves cracking open their user registry hive and doing some fixing as there is no UI to manage it. Paste the code bit into notepad and run it as the user after giving them local admin rights (or just edit their hive manually) so that these are the only entries.
As to the cause I think that users may have used the "Open with..." option on the right click menu and just picked a program. Either that or Firefox went off the rails again. Either way Windows should have prevented junk like this from happening.
Windows Registry Editor Version 5.00