I don't use Locations, but have had a play with it so as to be able to give you some feedback.
When I launched it, I found that, bizarrely, the only map already downloaded was "France V 5.757". This is odd because I am confident I played with Locations many months ago, certainly prior to recent firmware updates, and had the United Kingdom map on the phone too. Anyway, I downloaded the United Kingdom V 5.757 map without any issues and it all seems to run as expected.
You say you've tried using Settings -> Applications -> Manage applications to clear the cache. On my phone I see several apps listed that appear to be parts of Location, so I wonder whether you've cleared the cache and data for all of those?
You also say you've deleted the existing maps but that they seem to come back. I assume that you're deleting them from within the app, but have you used a file explorer app to delete them directly from the SD card? It's hard to understand how old versions of the maps can come back if they've been deleted, so I wonder whether the app isn't really removing them, maybe only hiding them.
On my phone, the maps are being downloaded to the following location:
/sdcard/.data/navigator/Data/Maps (note the dot before "data", meaning that you'll have to unhide hidden directories for it to become visible)
The maps are stored as "France.cmap" and "United Kingdom.cmap"