I had this problem at first too but got GPS working. You need to go to System Settings -> Google (Under Accounts) -> Location Settings and turn the option to let Google apps access your location.
Thank you for this suggestion, but I was already aware of this requirement. I have emabled access for Google apps in the location settings, but GPS is not functioning at all. I'm not sure if you saw all the screenshots, but this isn't just a problem in Maps, no application, not even ones designed to test the phone's sensors, have any GPS functionality.