Well Basecamp reported that the downloaded map needed unlocking, but even though my device was registered at MyGarmin and was detected correctly it wouldn't unlock online. I spent 30 minutes speaking with the Garmin Helpline and although they didn't fix the problem they gave me enough info for me to get the map working by hacking the map from the Nav V.
They emailed me a unlock code and a GMA file to unlock the map in Basecamp, but it still wouldn't work. The map in Basecamp actually had a slightly different naming convention and version number (see screenshot) than the one on the Nav V and I think this is why the unlock wasn't working. Anyway I used some software called Gmaptool to convert the gmapprom.img file on the Nav V to a format that Basecamp can read on the PC. I then used the unlock GMA file that Garmin emailed me on this extracted version and it worked. This proved the unlock code I was given was for the map version on the Garmin and not the one on my PC.
" />">

It looks like Garmin Express has downloaded two slightly different maps, one for the Nav V and the other for the PC. Should these be identical if they are downloaded using Garmin Express at the same time?
Looking at the maps in detail the differences are shown below:
On the PC - Map ID 3222 City Navigator Europe NT 2014.40 Version 17.40
On the Nav V - Map ID 3223 City Navigator Europe NTU 2014.40 Version 20.14