When you create a new Database in Exchange 2010 you also need to add special rights to this database for the Blackberry Enterprise service account (standard: BESAdmin) to this database.
Source: http://btsc.webapps.blackberry.com/btsc/viewdocument.do?externalId=KB02276&sliceId=2&cmd=displayKC&docType=kc&noCount=true&ViewedDocsListHelper=com.kanisa.apps.common.BaseViewedDocsListHelperImpl
Click Start > Programs > Microsoft Exchange Server 2010 > Exchange Management Shell
Execute the following command:
Get-MailboxDatabase | Add-ADPermission -User "BESAdmin" -AccessRights ExtendedRight -ExtendedRights Receive-As, ms-Exch-Store-Admin, ms-Exch-Store-Visible