We have recieved word that Grim Fandango dosn't always run with the latest version of DirectX installed, and this alone can prevent it from running in some cases.
If this is the case for you, then uninstall your current version (at time of writing v9.0) and install DirectX 6.0
Edit by Thrik (July 30th, 2007):
Note that this will
prevent most games from working nowadays, so this isn't recommended unless you're using an old machine dedicated to playing older games. In addition, DirectX 9 and DirectX 10's backwards compatibility should be a little better than when this post was written.