The Locations app is the stock HTC map app. There's also an app called Maps (which is Google's) and, on mine, another also called Maps, which is provided by Orange. I'll assume you're referring to the HTC Locations app and not any other.
First thing to try if you haven't done so already, Menu > Settings > Location > Reinstall
If that doesn't work, connect the USB/data cable from your phone to a computer that's linked to the internet. On the phone, select the 'Internet pass-through' option. The 'Internet pass-through' option seems to help in bypassing some download problems. (Ensure you have an internet connection by turning off Wi-Fi and Mobile data, and connect to a webpage.)
Then, in Locations, Menu > Get more > Select Download maps (3rd icon along from the bottom) > Europe > Select the map you want to download > When you get the 'Connection options' screen, select 'Download via Wi-Fi or cable only' and follow the instructions accordingly. It will probably take a while to download as together the stock UK/Ireland/France maps are about 1.5GB in size.