I had this same problem this weekend. The only way I could get it to start working again was log into my BIS and delete all my mailboxes, and reset them up from scratch.
how do i get to BIS? Im a noob to all this so lay terms plz...lol
GO here & either login (if you have a user ID & password setup already) If NOT create one. You will need your pin which you can find on your Storm under Options>Status. After you are logged in you should see your email accounts & be able to delete & recreate them & then resend the service books as well.