Me ha ocurrido dos veces, igual que a tí. La primera vez no me sincronizaban los contactos y tuve que formatear y la segunda no me sincronizaba gmail y también terminé formateándolo. Probé a desinstalar las últimas aplicaciones, reiniciar, etc y no había manera.
Con windows quizá cae un formateo al año pero con android voy casi a uno cada dos semanas...