The basics of languages are just rules: one memorizes words and grammer. Maybe in German there are more grammer rules than in English, for example, and more pieces to the vocabulary that must be memorized, but the rules are consistent, so overall I would say German is likely not that hard.
Anyone can memorize with effort, and things that seemed completely insane, might but a few months later seem quite natural (for example German plurals compared to English plurals).
The real difficulty is with words and phrases that are not a 1-to-1 matching with the native language, and aren't a simple memorization (for example English lacks word genders, but there is no mystery in how to use genders once they are memorized).
English and German are quite similar, actually. With straightforward memorization, an English speaker can directly become conversational at a party.
The difficult ledge to surmount is sounding intelligent, and not having to dance around and clarify statements. When to use words like "doch" or "mal", for example, when a 1-to-1 translation from the native language doesn't need that "filler". When to use verbs that don't have a clear 1-to-1 relationship, changing how one thinks about prepositions...the scary unknown of bridging that gap into thinking in a foreign language.
It's quite hard to think in another language rather than a 1-to-1 translation, since normally when trying to communicate, even if one has the rules memorized, one speaks without thinking. One must memorize whole phrases 100 times at least---it's a harder, more rote memorization than what I spoke of before. Maybe English is not the right language to explain these thoughts, since it (or I) lack the distinquishing words ;-p
If German, compared to the native language, has more cases, and thus requires more distinction where the native language has none, that is quite hard. There are more prepositions, for example. Or the difference between "kennen" and "wissen", or "Zeit" and Mal.
The second hardest thing is listening comprehension, since one's brain is so hard wired to interpret word sounds in one's mother language. Try listening to songs in another language and see if you don't hear phrases from your mother language! When listening, one has so little time to process information. It is overwhelming compared to reading at one's own pace. Furthermore, the information is of much lower quality. I read a linguist who once said that it's amazing we can communicate at all, considering how much context we use to understand spoken words.
[This is just based on my experience compared to learning other languages. For some reason I've found German the most natural of all, and that is really what counts for the individual on whether something is "hard" or not. I definitely feel right now, after a couple years and getting to a point of fluency that still feels like fast 1-to-1 translation, that German is hard, I'm just not sure that it is the fault of German.]
@Gigili: (ich konnte keinen Kommentar für dich lassen)