Not that you are in this boat, but, I have users who complain of this occasionally and they simply aren't waiting long enough for the reconciliation to complete.
I believe even if you use the reconcile now feature, it isn't necessarily immediate.
Outlook in Cached mode often factors a delay into the mix.
I have had to remove and re-add at least one user to the BES server in the past to correct this type of situation. Clearing statistics and removing all BB info from the mailbox when you do this and wiping the handheld clean.
Are you sure your server is sized correctly? Can it handle the number of users you have on it? Are you using MSDE (Desktop SQL server) with more than 150 users?
Make sure your MSDE (if you are using it), BES, and Windows server, is up to date with patches.
Good Luck.