One thing to try is to go the other way around. Pair your Mac FROM your mobile, NOT from your Mac. Then go to your Mac and try to sync again
This worked for me once when my K750i suddenly stopped syncing. I just removed device, then synced to my ibook from my phone and it was up and running again. Someone on this forum told me
Now I have a W800i and it also syncs without problems, so you shouldn´t have any problems
Good luck
PS I also run 10.3.9