Are you using UddeIMs CB plugin or CBs Private Message System? If not using CBs Private Message System then please unpublish UddeIMs CB plugin and try using ours. All we're doing is calling the below UddeIM API function.
Code:
uddeIMgetInboxCount( $userId, 0, 1 )
CB it self is doing nothing beyond that to retrieve the count. Looking at UddeIMs CB plugin its code is out of date and not using UddeIMs API call above, but is using a query directly that is not accounting for trashed or archived messages.