I had tried everything but the battery pull and holding it up in the open street (I was outside initially, but close to my house and some trees) several times, waiting until the GPS would just tell me '0 satellites found.' I don't know if one or both were the fix, and after a day of fussing with it, I don't care if it was the '4-lettered-word magical invocation' I cast over it, as long as it works now.
I also thought the permissions under Google Maps didn't look right (Allow under Connections - GPS was highlighted in bold, no others were) even though it had prompted me to 'Save' after I made the changes when I installed Google Maps. However, that should not have made a difference with Refresh GPS, I wouldn't think.
That battery pull/restart has been the end fix for a lot of head scratchers with my Curve and my wife's Pearl.