In Europe, it's more complicated since there's both new allocations and re-farming of existing allocations, and also the existing 2G/3G allocations are not the same between the different operators.
For example, in the UK where we have four operators:
Operator | 2G | 3G | LTE |
EE | 1800MHz | 2300MHz | 800, 1800(ex-2G), 2600MHz |
Three | No 2G | 2300MHz | 800, 1800(Purchased from EE) |
Vodafone | 900MHz | 900(ex-2G), 2300MHz | 800, 2600MHz |
O2 (as currently used by Tesla) | 900MHz | 900(ex-2G), 2300MHz | 800MHz |
LTE allocations above are what they have licenses for; not necessarily using all of them yet - not least because customers don't yet have phones for them (iPhone5 for example supports LTE on 1800MHz but not 800MHz).
The Model S definitely supports 900MHz and 2300MHz for 3G and 900MHz for 2G, probably 1800MHz as well. They would have no reason to have antennae suited for 800MHz, unless for deliberate future-proofing.
So my guess would be that if you upgraded the radios without upgrading the antennae, you would get LTE in some areas but not all. However, if you are looking to LTE for coverage rather than throughput it's likely to be that missing 800MHz that's most important.