.. and 5 minutes later I figured out how to fix it!!
I checked the log and looked through the 25 "records" being updated. Tried to figure out what was different.. I had added a recurring calendar event ("Mum's Birthday") and a recurring task ("Pay car loan") and I deleted both of them and it updated fine!
I've previously only put birthdays in via Outlook, and it seems to go to the handheld fine, but apparently not the other way around.
So hopefully this monologue wasn't in vain and someone with the same problem will benefit