GPS stopped working after upgrade to Gingerbread

I went into a T-Mobile store and had an associate upgrade my handset to Gingerbread. Everything works fine except for when I go into Navigation to use GPS. I type in the location where I want to go, but it says, "Searching for GPS..." and then it never finds it. Of course, I'm trying to use it in locations where GPS previously worked fine.

Here's what I've done to try to fix the issue:
1. restart the phone
2. download an app called "GPS Status & Toolbox" It has a tool that allows you to reset your gps data or something like that.
3. factory reset

Does anyone know of something else that I can try?

 

Just wanted to update this thread just in case anyone else is having the same problem.

I called T-Mobile tonight, and they couldn't give me an answer on how to fix the GPS. But the lady mentioned that others were having the same problem, and they were working on a solution. I asked her how many people were having this problem, and she said ten. That's not exactly a huge number, so I don't think I'll hold my breath for a fix. Right now I'm considering rooting my phone and installing CM.