I've had the same issue from time to time, what I have found that works is:
1. Stop the sync contact feature for FaceBook, Twitter, etc.
2. Let your phone sit for several minutes, around 30, to ensure all old contact info is removed.
All you should have left is Gmail contact's
Then one at a time, turn the Sync back on, but let each app finish before you tunr the next one on. This should clear up some of your issues, however, if the spelling of the contacts name and\or email address is not the same as what they have on the profile page for FaceBook, it will not sync correctly and you will have to manually 'join' them.
So before you go to the trouble of un-syncing, you may want to veryify that information first, it could be as simple as that.