My phone is a Nexus 4, running Android 5.1.1. I am getting this error when I try to go to a postcode in London.
No network connection
Can't connect to the network. Check your data connection and try again.
Cancel Try again
But I have downloaded offline maps of London and surrounding areas.
e.g. if I go to "My Places", I can see 3 offline maps, including London*
@Czar points out that the map files seem rather small...Maybe that is the cause, though I have an issue there too. It doesn't give me a box to draw around what I want to download, it gives me a screen where I zoom out to how much I want, but if I zoom out too far it says it's too big. It is only letting me save areas that are quite small like around < 30MB.
*Note- in this question, I stated that I clicked 'My Places' to see offline maps that was the case in the version I had, where I had the issue. The current Google Maps has offline maps in the menu. Google Maps can be updated from the Google Play Store.