Had a simular problem like this.
It's a simple fix if you know where to look.
You can do it in two ways.
Way 1: Use this program
Repair .Lnk Association
Way 2: Use regedit
Start Registry Editor (Regedt32.exe) and select the following subkey:
HKEY_CLASSES_ROOT\.lnk
From the Edit menu, click Delete.
On another Windows NT 4.0 computer, start Registry Editor (Regedt32.exe) and select the registry key HKEY_CLASSES_ROOT\.lnk.
From the Registry menu, click Save Key.
Copy this file to the computer exhibiting the problem or to a floppy disk.
On the computer exhibiting the problem, recreate the registry key by selecting HKEY_CLASSES_ROOT and then from the Edit menu, click Add Key. Type .lnk for the key name.
Select the new key, click Restore from the Registry menu, and select the file from the other computer or floppy disk.
Quit Registry Editor and restart the computer. Test a Program menu item or shortcut.
To manually enter the information, perform the following steps:
Start Registry Editor (Regedt32.exe), select the HKEY_CLASSES_ROOT subkey, and then click Add Key on the Edit menu.
In the Key Name box type ".lnk" (without quotation marks), and then click OK. Note that you should leave the Class box blank.
In the Add Value dialog box, click OK to leave the Value Name blank, and click REG_SZ in the Data Type list.
In the String Editor box, type "lnkfile" (without quotation marks), and then click OK.
Select the .lnk key you just re-created under the HKEY_CLASSES_ROOT subkey. On the Edit menu, click Add Key and then type "ShellNew" (without quotation marks). Note that you should leave the Class box blank.
Click Add Value on the Edit menu, type "command" (without quotation marks) in the Data Name box, click REG_SZ in the Data name box, and then type "RunDLL32 AppWiz.Cpl,NewLinkHere %1" (without quotation marks) as the string value.
Quit Registry Editor, and then restart the computer.
