Another way the GPS issue is related to poor cell phone service is that they're both symptoms of the same situation. If you're deep in some concrete jungle like Vegas, you're not going to have great cell signal, and a GPS satellite isn't going to be able to find you to get a fix. My office building has both issues, so my only options while I'm at work are to put my phone in airplane mode or just leave it charging all day.
BTW, I went ahead and rooted my phone and fixed the problem that way... For what it's worth, the rooting process really wasn't that bad, but you do lose everything when you do it, so backups (in triplicate) are advised.
If anyone's curious about going the rooting route and wants to know what you have to do after you've rooted, let me know. I did a fair amount of research and discovered multiple solutions. Can point you in whatever direction you want to go.