Comment # 7 on bug 58383 from Patrick Ohly

(In reply to comment #6)
> Hey Patrick. Any news? Still cannot sync. Happy new year, by the way.

I didn't consider this a bug in SyncEvolution and therefore didn't pay much
attention. Did you file bugs against your distro regarding this?

Now that you asked again, I remembered something:

https://bugs.launchpad.net/ubuntu/oneiric/+source/obexd/+bug/872044/comments/62

Is that likely? You did not respond to my question whether you had made other
changes to your system, like updating the kernel.

Workaround:
sudo hciconfig hci0 sspmode 0

Try unpairing and re-pairing after that.