this thread might help?
http://www.lemmingsforums.com/index.php?topic=590.msg12559#newDid you download the version from in the thread Luis posted? In that thread ccexplore has a link to the version which includes needed files to get it to work properly. If it doesn't contain these files it won't work at all.
btw, the shortcut doesn't hurt anything. I have a shortcut on my desktop and it works fine. As long as the location of the program files (exe and stuff) is in C/ that's fine.
I just might make a help tutorial on how to use Lemmix because it is difficult and there's not much documentation for it.
----ALSO important note-----
In Lemmix there are 3 options windows that you can move around the screen. (F10, F11 and F12 pressing these bring up options like entering how many lemmings are in your level). You can move these windows to the bottom panel. They will 'snap-to' the panel, however: DO NOT reposition the lengths of the bottom panel sections themselves. Doing so will stop most of the hotkeys from working (like Delete). This caused me undo headache for three months until I figured out what was going on. why this happens apparently nobody has any idea.