You may have lost your service books after you removed the battery. I lose my service books after EVERY reboot. There is an issue with that. Hopefully they'll be corrected with the a new OS update.
Try these steps...........
I'm not sure in the first step will apply for you because you have Fido?
First
Options>Advanced Options>TCP/IP>click BB button>Reset to Defaults
- Keep the APN Settins Enabled the same as is
- Check the APN Authentication Enabled
- Type
for Username
- Type cingular1 for Password
- Click BB button and Save
Second
Go to Service Book>Click BB button> Show Keyboard>Type 4?2?
- When the Legacy Restored pops up, click OK
Last
- Connect the phone to DM, reinstall the service book, and resend the service book from BlackBerry Internet Service