Surely someone has a fix for this.
Try renaming the shortcut to just "Adobe Media Encoder" -- no .exe or .lnk in the filename.
If that doesn't do the trick, read through this rather lengthy thread: http://forums.adobe.com/thread/717697. It includes a couple other solutions.
That did the trick - no .exe or .lnk