I think you're talking about two different things...
An "old" Western Europe map (pre-v875) definitely has Germany on it.
The new Europe map is so large that it is also available in zones for machines with limited memory capacity (i.e. most of them!), but you are entitled to all the zones , so that's not a huge problem.
There's a bit of unhelpful confusion in the naming in that link you posted... there is a "Western Europe" map and there's a Europe map with a "Western zone". There isn't really a "Western Europe Zone" (even though the email from TT described it like that).
A better link is here:
Map zones.
-----------------------------------------------
But stuarttre says he cannot find ANY locations in Europe.
stuarttre... have you actually switched maps to the Europe one using "Switch map" in the Preferences menu?
If you have, can you give us the exact sequence of button presses you are doing to find a location?
There's got to be something fundamentally silly going on. You should definitely be able to see the Europe map in "Browse map and be able to "Find" places in Europe on it, even while you are still in the US,
But it will only work once you have switched over to it.