Rather than debrand, this could have been solved by going under options, advanced options, host routing table, then hitting the menu button and selecting "register now." Sometimes a battery pull is required afterwards.
Posted from my CrackBerry at wapforums.crackberry.com