Cannot send or receive mail on Blackberry Device for mailbox on newly created Exchange 2010 Database

So you created a new Exchange 2010 Mailbox Database but all mailbox users you move to or create in this database cannot send or receive mail on their Blackberry device?  Permissions, permissions, permissions…