I'm in Pennsylvania and I did a soft reset. Blackberry Maps has working in the three weeks I've had the phone. I've gotten these messages a couple of times but it seems to be not working now.
yes the GPS is enabled. I was just outside and this time the error message I got was that it wasn't available in my region. Then the next time I tried it worked.