You do not need to go into your Sync accounts, erase data, clear cache, Facebook settings, etc...until HTC gets it fixed, all you have to do is manually set your date on your phone to say its any date before 2013.
That's not realistic. Having the correct date and time is much more important than having Facebook contacts synced.
Two solutions:
1) delete Facebook data, clear data for contact storage, re sync contact data from Google, open Facebook and login and chose not to sync any contact data.
Or
2) De-friend the person who had a leap year birthday, follow steps in 1) above except sync your Facebook contacts. Then once HTC fixes this re-friend the leap year birthday person.