Rosetta Stone Japanese - A good tool
Rosetta stone has worked fairly well for me. A number of the negative reviews here don't match up with my experience. I've dealt with the technical support on installation issues (number of seats), and they were very helpful and resolved the problems fairly quickly.
Learning a language is a difficult task - no software or course will take you anywhere near fluency - they are a good way to get started in a structured way. You'll need to supplement any course out there with grammar books, verb books, vocabulary books, etc, as well as help from native speakers.
Rosetta stone did a good job of what I hoped it would do - it got me started in a structured way. I found vocabulary easier in commit to long term memory with Rosetta stone than other courses and methods.
I used Japanese. Rosetta stone has a HUGE major advantage over other systems I've seen in that you can review the course materials in Kanji, Romaji, or Kana. Virtually every other course I've seen just uses the Romaji. Learning Kanji is a very difficult task in my opinion for an english speaker, but you'll feel very lacking if you go to Japan only knowing how to read and write in romaji! Software like the Tell Me More may be great for something like spanish, but it only has Romaji per their website which really limits its usefulness in my opinion.
The fault I find with Rosetta stone Japanese is that they stick to one formula for the instruction across languages. Their formula works well with european languages, but patterns of conversation are too different in Japanese, so occasionally you get a sentence that a native speaker would never say (pronoun usage).