I also had the same problems.
Have around 160 contacts, fixed most using Shubaroo Contact Fix (as mentioned before).
But I also got 35 contacts which were reverted back to Last Name, First Name after next sync.
Found out that all these 35 had something in the "notes" field (mostly birthtdays which were imported from outlook, and were already wrong be 1 day somehow.....)
* Cleared all notes
* Synced mobile
* Ran contact fix
* Synced again (35 contacts changed = OK)
* Synced again (0 changes = OK)
* Synced again and again and......

Problem fixed for me.

Hope this will help some of you as I agree it is very annoying.