I think you'll also find that it depends on the person in part too. Speaking from personal experience, (with my mother tongue being English), I found French to be near impossible to learn. Italian was a lot easier to pick up as was Latin. Although I've pretty much forgotten both now as I never use them anymore.
Mandarin, Cantonese and various other Chinese dialects were fairly easy to learn to understand what was being said, but the tones were a real challenge to reproduce when trying to speak. Not surprisingly, I soon gave up on those languages when I ran out of time to really dedicate to them.
Japanese, on the other hand, was very easy to pick up. The basic grammar is some of the easiest out there. Unlike say English, where it feels like there are more irregular grammar patterns than regular ones, Japanese only has a handful of irregular patterns. Everything else, is pretty much a simple case of following one of two rules for conjugating, etc.
ilves mentioned the differing levels of politeness as a barrier to picking up Japanese, but the "good" news here is that foreigners are simply not expected to master most levels of politeness. As long as you can differentiate between when to use a dictionary form and a ~masu form, you'll be all set.
The higher levels of politeness, termed "keigo" are something that even Japanese themselves will struggle with, and they tend not to learn the proper usage of these terms until they graduate (generally, keigo is learnt during the first month or so of employment and is taught by the employer, not at schools).