Hi Guys,
We managed to resolve the issue, we had to pull in Zimbra support ( They were awesome )
The problem was due to the fact that we recently added proxying to our cluster server's, and the BES connector cannot operate behind a Proxy
Related Bug >
Bug 33179 – BES and Proxy
We had to turn off proxying on one of the cluster boxes, Move the admin account BES uses to this Box, and configure the plugin to connect to this box directly ( instead of our clustered hostname.hosted.com server name )
Also did a cleanup on the BES server, reinstalled Outlook, updated to SP2, removed and reinstalled BES connector, ensured Outlook set to use GAL for lookups.