Okay, I understand your point; but still, I think Europe is really easy (and I'm not a top player, mind you; and I just re-played it to make sure that wasn't pure luck), and any problems that anyone might have had with it probably come from not using airlift cards, or not knowing you can airlift reinforcements to ally - maybe just bold that part about them in the introduction, or something.
And I'm not against naming the challenges something else than "Challenge #"; I just dislike the names you've chosen. Maybe use some less "crazy" adjectives - for example, "Impossible", or some synonyms:
http://www.yourdictionary.com/synonyms/impossible - just think about how "Inconceivable" or "Hopeless" sound, and how apparent it is that such levels are barely passable. Also,
http://www.yourdictionary.com/synonyms/difficult - "Ambitious".
I hope you'll use my suggestions :D