I had this problem some time ago and applied the above fix. I just got a new hard drive and re-installed PPro 5.03 to the new HD. When I tried the fix, it didn't seem to help, as I'm still getting the error message when I start up the media encoder. I have tried renaming the shortcut to .EXE, .LNK, .EXE.LNK, but to no avail. What am I doing wrong, or is there a different fix now.
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.