Found my son watching a youtube video of Grim Fandango yesterday and surprised him by plunging into my archives and bringing out the original CDs: loved that game.
After struggling with this to get it running for a while yesterday with Wine, I found ResidualVM: http://residualvm.org/
This is a native, open source rewrite of the underlying game engine for Grim Fandango that runs on Linux, Windows (newer versions), and Mac in both 32bit and 64bit. You just copy the data files (don't need any .exe's etc.) from the CD's to your system, then run the ResidualVM program instead of the Windows programs.
I played well into Year 2 and it worked perfectly for me: all music, dialog, sound effects, video (with 3d enabled), save/restore. Not one single glitch, restart, or futzing around. It will manage the 1.01 patch, too, just drop it into the same directory as your data files.