But it's still "the most difficult language to learn". So it's worth taking that difficulty into account. For example one can learn Spanish, Swedish and Vietnamese in around the same amount of time it would take to learn Japanese.
But, there's an important distinction. Japanese is singled out as "somewhat more difficult for native English speakers to learn than other languages in the same category."
Phonologically, Japanese is easier. No tones, and no retroflex consonants to worry about as in Mandarin (unless you don't mind sounding southern/Taiwanese). There is a pitch accent in Japanese, but apparently it varies wildly from one end of the country to the other, and it's not generally critical to comprehension, unlike Mandarin tones.
Lexically, Japanese is easier, at least IME. Don't know a word? Given all the borrowing in Japanese, I've had very good luck just to mangle the English word into Japanese phonotactics, and 90% of the time, the person I've spoken to immediately knows what I mean.
Syntactically, there's a lot more similarity in Mandarin's basic SVO word order to English.
But Kanji. OMG. You need to learn roughly the same set of Kanji as hanzi to be high-school literate, but the Japanese set will generally have a minimum of two pronunciations per character, which vary wildly in context. Mandarin generally has one pronunciation per character, which becomes far simpler to learn.
Those are a mixture of my impressions, and the opinions of friends who speak the language (both learned and native). Overall, I think the most difficult part of mastering Chinese and Japanese is the same: Lack of shared cultural context, if you come from an English-speaking or European country.
Spoken Japanese, though, is easy. Well, at least from a mechanical standpoint. Japanese grammar is dirt simple and minimalistic, and I found it shockingly easy to learn. However, as someone else mentioned elsewhere in the post, Japanese is very big on inferring as much as possible from context and only speaking what can't be inferred. It can honestly be a chore just to determine whether a sentence is in the first person, the second person, or the third person, because Japanese is so aggressively pro-drop that most of the time, that information has to be inferred from context. And if you intend on speaking Japanese yourself, there's a lot of subtlety when it comes to picking the appropriate register to speak in. Use the wrong verb endings or the wrong pronouns (in this case, I'm glad Japanese is so aggressively pro-drop), and you'll stick your foot in your mouth.
[0] Most people use it as a dictionary, but it also has a really awesome glossing mode: http://www.edrdg.org/cgi-bin/wwwjdic/wwwjdic?9T