Try registering your device, *Register Device: Click options> click advanced options> roll down and click host routing table> press your menu key> select register now> click back and close.
Posted from my CrackBerry at wapforums.crackberry.com
Do what exelant pointed out, and if it doesn't work pull the battery from the
phone while the phone is ON. I've had my BIS services not work when I was
a rookie and thought BIS was down too. The battery pull solved it.