Your link points to a Windows 95/98 version and I guess you have at least Windows 2000 or XP. You should try the NT version here.
Alternatively use a little VBScript that you can call from the command line:
set objWSHShell = CreateObject("WScript.Shell")
set objFso = CreateObject("Scripting.FileSystemObject")
' command line arguments
' TODO: error checking
sShortcut = objWSHShell.ExpandEnvironmentStrings(WScript.Arguments.Item(0))
sTargetPath = objWSHShell.ExpandEnvironmentStrings(WScript.Arguments.Item(1))
sWorkingDirectory = objFso.GetAbsolutePathName(sShortcut)
set objSC = objWSHShell.CreateShortcut(sShortcut)
objSC.TargetPath = sTargetPath
objSC.WorkingDirectory = sWorkingDirectory
objSC.Save
Save the file as createLink.vbs and call it like this to get what you originally tried:
cscript createLink.vbs "C:\Documents and Settings\%USERNAME%\Desktop\Program1 shortcut.lnk" "c:\program Files\App1\program1.exe"
cscript createLink.vbs "C:\Documents and Settings\%USERNAME%\Start Menu\Programs\Program1 shortcut.lnk" "c:\program Files\App1\program1.exe"
That said I urge you not to use hardcoded paths like “Start Menu” since they’re different in localized versions of windows. Modify the script instead to use special folders.