I've got the Bold 9650 on Verizon and have been having issues with any GPS related services over the past few weeks. I believe all of my settings are correct but every app that has the ability to use location does not seem able to connect with the GPS. Google Maps will occasionally work but that's about it. BB Maps, Weatherbug, GoogleMobile app, Bing, etc, will not connect.
And what OS are you using? I'm on 6.0.0.280 and I find that Google Maps pinpoints my location a lot more accurately than before. So far, I haven't had any problems.
Go to an open field or area with good view of the sky.
Menu/options/status and then type "test" without the quotes. You will not see the typing. It will open a test module. Under the menu, you can test the gps. I believe you have to hit the trackpad to begin the gps test.