I was getting an error with CreateShortcut "$SMPROGRAMS\Program\Link.lnk" "$INSTDIR\PROGRAM.EXE", and I believe someone else around here was having the same problem with a client.
I've figured the problem out. You need to CreateDirectory "$SMPROGRAMS\Program" first.
Is this a bug? Surely you should be able to create a shortcut in a non-existent directory and have the directory created automatically?