Possibly a stupid question but in the maps settings do you have it set as 'online'? I get that message if it's offline - if 'online' isn't selected it won't use any network connection even if you're connected.