Hi, it's bad news I'm afraid. I have a Desire S which I haven't used for some time - I've upgraded to the One. I used Locations a lot and have a lot of maps downloaded. I've just tried to download a new map and although I don't get the same message as you I get a download warning and the download hangs in 'pause'.
I have just spoken to HTC and they are no longer supporting Locations saying that it's a 'third party app'. I already knew this because Locations wasn't on my HTC One and I queried it with HTC back in June, but not having tried to download any more maps to the Desire S didn't realise the full implications.
So the bottom line is you're stuck with the maps you currently have on your device.

It is possible to access the map folder on the SD card with your PC/Laptop so you could quite probably copy map files into it.
I have maps on my Desire S covering most of Western Europe and United States. What countries were you particularly interested in ?.
I've just uploaded the Malta map to dropbox so you can give it a try it. Let me know if you're not sure how to access the map folder. **
https://www.dropbox.com/s/oozc9db38ahx4hm/Malta.cmap
**PS might as well post it now (assuming it's the same on the Sensation - it should be),
Connect to PC/Laptop - select Disc Drive,
copy/paste into :- .data --> navigator --> Data --> Maps
If anyone else is interested we could perhaps start a 'map swap' thread !!
