Sadly, I'm guessing I'm too late for you, but hopefully I can be in time for anyone else running into this.. We had the same problems and had to follow the instructions at:
Blackberry Stops Sync After Updating Outlook to SP2 - Zimbra :: Wiki
We were seeing the exact same behavior after upgrading to 5.0.18 and after we followed the instructions in the wiki, it seemed to work just fine.