The challenge is always in expression. Languages must be fit for purpose. When used in situations that require complexity, for example legal documents, Acts of Government and financial correspondence, the language must have adequate complexity to fulfil the types of nuance required in these situations, and because languages have evolved differently, the methods by which the precise definitions and differentiations required are achieved vary.
Since we have sideswiped Christian's discussion, his homeland is an interesting example. Luxembourgish is a language which is still developing out of the Mosel-Franconian dialects of German it still has close resemblances to. It has now been accepted as a national language, and therefore you are free to express yourself in court, in parliament etc. in Lëtzebuergesch. However, the language has a few characteristics that limit its usefulness as a legislative language. Christian can help me out here - it's been a few years since I covered this - but I think there's only one form of past tense - the perfect - in Lëtzebuergesch. This is a linguistic feature which makes it easy to use in everyday life but means that in situations where complex language is called for, a majority of Luxembourgers still prefer to use French (more commonly) or German (less commonly). Lëtzebuergesch is still developing the vocabulary required to make itself more usable in these situations, however it is likely that much of this will simply be borrowed from the neighbouring languages.
The other question simply is about what is meant by complex? We see speakers of particular languages talking about the complexities of their own, but it's only a relative measure. Pistolero was talking about how tough Dutch is to learn, but for a speaker of German or English, it's a lot easier than, say, Mandarin or Hebrew. For an Afrikaans speaker, it's probably extremely simple to pick up. Hitch talked of people having problem with the range of palatal consonants, fricatives and sibilants in Polish, but to speakers of other Slavic languages they're more likely to find the nasal vowels ą and ę an obstacle than those consonants. Usually what's difficult is not necessarily complexity in syntax, morphology, vocabulary or phonology, but what is different to the learner. For example, first-language Arabic speakers can often use ع as a shibboleth, as the sound it represents is uncommon in other languages and therefore for most people it is a sound that has to be learned; languages without T-V distinction can often find problems when learning in using the inappropriate 2nd person, while trying to learn a Uralic language will forever result in a struggle with the numbers of case endings and what they represent, whereas on the other hand first-language Hungarian speakers trying to learn, say, Spanish, may find it difficult to express themselves due to the need to learn a bunch of separate vocabulary to create prepositional phrases or even entire sentences in order to explain what a case ending does for them in their native speech.