So, when urbansling points me to a game that is compared to Grim Fandango by its reviewers, it immediately got my full attention.
The name of the game is "Syberia", is developed by a french software house called Microids. It's impossible to quote the reviews and tell you what the game is about, and not make this article 2 screens long. So if you're at all interested in adventure games, then do yourself a favor, and check out one of the reviews or the official site.
Everything about this game looks pretty good. It has awesome artwork, great music, a pretty original story as far as I can tell, and the best news of all: Release date - May or June 2002.