ok, now do this (I probably should add this to instructions in the initial post, but it is mentioned in several subsequent post in this thread for this:

On your BlackBerry
1. Go to Manage Connections > Mobile Network Options > Network Mode > change 3G & 2G to be 2G only and escape out.

2. Then go to Manage Connections > Mobile Network > and UNcheck your service, wait for it to show OFF in the signal indicator area at the top of your screen.

3. Now, return to the same Manage Connections > Mobile Network > and CHECK your Mobile Network to be back enabled. You may have to do this 3-5 times, each time being patient for the OFF signal indicator. Then give the device five minutes to gain EDGE. If it doesn't rinse and repeat #2 and 3 here.

You should be ok from there once it reaches EDGE again.