As I've now joined the ranks of people that have gotten this error code I thought I would document my attempts to fix it and hopefully this will save people some searching.
First off - it appears the cause of my problem was creating a partnership with a second PC. And the solution was posted here:
It sounds like this bug is specific to Windows Mobile 6.1. It also sounds like there is a fix available to phone manufactures but it is up to them to provide an update for your phone.
If the above doesn't do the trick try the steps below one at a time - hopefully one of them works. For each step, disconnect your device, follow the step and then retry synchronizing. This are collected from various posts online (most of which I tried).
1. Delete the 2nd partnership from your phone
Launch Active Sync on your phone while you're not connected to your PC, open the options and delete the second partnership if you have one.
2. Disable Advanced Networking
Start / Settings / Connections / USB to PC and unselect "Enable advanced network functionality". This worked for some, didn't help me.
3. Change Sync Settings from your desktop
Try unselecting Tasks, e-mail, etc and see if one of them is causing the problem. Note - if you unselect Contacts, e-mail, or Calendar it will remove all information of that type so uncheck the least important ones first. One user reported the problem went away when he created a new task on his phone - if you have no tasks and they're sycnronizing - give it a try.
4. Check Outlook on your desktop
Fully close Outlook and then open the Task Manager. See if there are any rogue instances of Outlook.exe running - if so - remove them.
5. Repair your PST file(s)
This is built into Outlook 2003 - for Outlook 2007 you'll need to run SCANPST.EXE which should be located in C:\Program Files\Microsoft Office\Office12. You'll likely have to manually select your PST file. Reboot and resync.
If none of these work we're getting into more drastic steps
6. Re-install Windows Mobile Device Center or ActiveSync
Find the latest version and re-install
7. Delete your Partnership
From both your device and from your sync software - delete the partnership. This likely means you'll lose any changes you've made from your device.
8. Create a new PST file in Outlook
Requires some working knowledge of outlook. Create a new PST file, set it as default and then try importing all of the data from your previous PST file. This should have the same effect as running SCANPST.EXE but some reported this worked. Reboot and re-sync.
9. Re-install Outlook
Shouldn't be necessary if you've followed the above steps but now we're trying to remove all possible culprits.
10. Hard Reset your phone
When all else fails - start over. Not a pleasant option. Check your manual for instructions on how to hard reset your phone. And please note, a hard reset will remove all installed data and applications - your phone with be returned to an "out of the box" state.