I changed mine in less than 3 minutes.

(on the AT&T/Cingular network)
Open your browser, click on 'Blackberry Start' (one the MediaNET homepage)
and then click 'Create New Username' and follow the prompts.
After that's all squared away, on your desktop, go to the page mentioned above (click AT&T) and enter the username and password you created from your mobile device, and VOILA! you can edit your mobile email sig. to your hearts desire.