I used this thread as inspiration to do a quick Google search for other hard to learn languages. Navajo seems to make it on a lot of lists, and the description given here is rather amusing:
http://matadornetwork.com/abroad/9-of-the-hardest-languages-for-english-speakers-to-learn/

I would imagine all Native America languages would be very hard because none of them have a common base like the romance languages and no doubt every single one of them comprises a completely unique alphabet and in some cases different concepts of words entirely. Example of that being (yes I know it's a different continent) the African bushmen. A lot of their words aren't even what most people would consider words but rather clicks and knocks. The real bushman who played a real bushman in "The Gods Must be Crazy" was named N!xau. How exactly do you teach that!?