Although intended for Japanese adults, this "game" for the DS is really good for those at the upper beginner level of Japanese and above. And by "above" I mean intermediate and advanced students of the Japanese language will get a lot out of this DS title. I'm relearning Kanji at a very rapid pace with this tool. As soon as I master the 1,945 Kanji in this program (probably by the end of summer or about six months after purchase) I plan to upgrade to the newer version, Nazotte Oboeru Otona no Kanji Renshuu Kanzenhan (なぞっておぼえる大人の漢字練習 完全版), which includes an additional 316 characters, a dictionary function, more mini games, and (hopefully) additional examples/usages of the 1,945 basic Kanji. (Note that these DS games are difficult to find in the USA, but you should be able to pick them up through YesAsia.)
Learning with the DS is far more entertaining and tolerable than the traditional methods of flashcards or Kanji guide book reading. I can do, and have been doing, Nazotte for a couple of hours a day (mostly while I have quick 5 minute breaks, am waiting in line, or am a passenger going somewhere), whereas flashcards or reading gets boring really quick, and I can't stand a couple hours a day worth of it. The nice thing about this game is it remembers what you are having trouble with so you can go back and review only your problem areas. This reduces or eliminates the number of your problem Kanji quickly.
I purchased one other DS game (pictured above and to the right) for my kids to learn hiragana and katakana (as I can't get them to sit down and write them out on paper to learn hiragana and katakana the way I did 20+ years ago), but I haven't played with it much. It is called Tadashii Kanji Kakitorikun Kanken Taisaku (正しい漢字かきとりくん漢検対策). It doesn't seem as useful for learning Kanji readings as Nazotte. I'll delve into it more once I've gone through Nazotte completely.
There are other DS programs out there for those learning Japanese. Kanji Sonomama Rakubiki Jiten (漢字そのままDS楽引辞典) looks great if you don't already have an electronic Japanese dictionary or if you have two DS consoles. I like having both Nazotte and my electronic dictionary in front of me at the same time so with only one DS console Sonomama wouldn't be of much use to me. 200 Man Nin no Kanken (２００万人の漢検) is another, but it gets mixed reviews on the internet. Also, there are many puzzle games out there like Mojipittan, but I'm guessing they are too difficult for even intermediate level learners.
October 2008 update: There is now a DS game aimed at English speakers learning Japanese. For more information on My Japanese Coach go here.
Screenshots and my review of Kanken 2 for Nintendo DS (漢検DS2+常用漢字辞典)
Exchanging US dollars into yen before or during your trip to Japan
Pictures from Japan
Where to stay in Japan
Professional Japanese Baseball
More things to read on Japan
More on DS learning Japanese games