I've been having this issue until I added relays through zmprov. Suddenly, all the blackberry desktop sync's worked. Now I cannot replicate this again because I don't want to mess with a live system, but maybe someone wants to test.
Follow the directions here:
I've updated the wiki with some of my observations and what I found on this forum.