I'M Not sure what to tell you. I live in orlando. I was in south florida last week though and I was using gps just fine then. The only thing I can think of at the moment that I haven't told you : download gps essentials. It has a feature that shows you the number of satellites in the area and how many are used to try and locate where you are. It may just be me, but it's also a lot faster at locking in on my location.
If this continues, even after re trying the steps posted above,i say your phone has a bad gps chip...
But just do everything again and try gps essentials. I'll keep my fingers crossed here.