I had this problem with Word
IMPORTANT NOTE BEFORE READING!!!:
I AM NO COMPUTER EXPERT BY ANY MEANS. IF ANY OF THESE FOLLOWING PROCEDURES DAMAGE YOUR COMPUTER SYSTEM OR HARDWARE, I TAKE NO RESPONSIBILITY BY ANY MEANS! FOLLOW AT YOUR OWN RISK!
I had that same problem with running Microsoft Word and Microsoft Excel. For some reason, the only way I could get those programs to start was to go to "Start" (lower left of screen) and go to programs, and your game should be under "lucasarts". Then click on "Play Grim Fandango". That usually starts the game with no problem!
Another thing you can try is to right click on the desktop icon and press "properties". Make sure that it says under "target", the name that you put down when installing it.exe. If this is incorrect, it can very well cause some problems.
If that doesn't work, go into "properties" again and click on the "compatability" tab. Click on the little box "Run this program in compatibility for:". Then select...I believe Windows 95 or 98 should be your best bet. (This will also be where some problems can occur, but they are usually pretty easy to fix with a "System Restore" if you run into problems!)
If that doesn't work, maybe trying to create a duplicated icon on the desktop is the only thing I can think of.
If that does not work, umm...try it on an older computer.
ONCE AGAIN: I AM NOT RESPONSIBLE FOR ANY DAMAGE THESE PROCEDURES MAY CAUSE, USE THEM AT YOUR OWN RISK!