We were having the same problem with our 8900's with Cingular. Went into the BIS setup and deleted the @mycingular.blackberry.com email account and then re-set it up. Seems to have soleved the problem. Cingular support stated that there were errors and asked me to delete the email account. At that point, we were disconnected so I never gout the actual error that he was seeing. I did not feel like calling back and waiting 15 minutes again.
Works now. Tomorrow may be a differant story.