Well I would like to thank those of you who have mentioned tightening the screws under the rear panel. I am amazed that could be the problem! I tried it on my wife's phone with it turned off. Only 1 screw in the bottom left even turned at all. It turned about 1/4 turn. Now the GPS on her phone locks rock solid in seconds! Its like night and day. I tried it on my phone while it was on and searching for a lock. It wasn't instantaneous, but before I could put my case back on I had a lock.. in my garage. I'd like to note my screws ALL turned a bit. My wife's only the one screw moved.
So to sum up - if you have GPS problems, tighten the damn screws first!