Nope, haven't updated the OS or anything yet. And no, haven't really discussed the exchange. They have this return policy where you pay 15 dollars and get a new phone, but the phone is sent to RIM and if they don't find anything wrong with it then I pay full out of contract price for the phone I received to replace it. (i.e. way more money than I want to spend right now...)
It is possible that it is just my phone, but not a single one of my friends with blackberries (4 or 5) on this network have gotten their GPS to work. Granted though they have only tried once or twice. Is there any way I could test whether it was just my phone acting up or whether Cellular South changed something on there network preventing it from working?
On a side note is the 8130 Pearl A-GPS? or regular GPS? would that make a difference here?