It appears that the Android 4.1.2 update made another subtle, but important, change to location settings / permissions for Google apps in that you are required to enable location settings in two places: once for device-wide location capability and another for Google apps. The first setting is in the usual Settings->Location->Access to my location, but now you need to also enable location access in the Google Now settings for Maps to function.

This can be done by bringing up Google Now (on devices without physical buttons swipe up, on devices with physical buttons hit the search button), then bring up the overflow menu (scroll to the bottom of the Now page and tap on the button in the lower right), then go to Settings->Privacy & accounts->Google location settings where you can enable or disable the setting. If it is not enabled, you will see a notification stating "please enable google apps location access" when attempting to get a GPS fix in Maps.

This change has a couple of interesting implications. First, location appears to have become an all or nothing option for Google apps and services. i.e. if you want location in Maps, you need to enable location in Now, Chrome, etc. Second, the text on the Google Now settings page indicates that you can allow Google apps to access location data yet disable non-Google apps access via the traditional settings page. This does not appear to work currently (i.e. Maps was not able to get a GPS fix with the main location settings disabled) but this may be a change coming in 4.2 or later.