Ive solved it!
But dont why it works, probably something that should be fixed in the OS.
Go to Home>Settings>Data Synch>Google> uncheck contacts. Wait a couple minutes then recheck. Then, once you get the error again go to Notifications> Too many contact deletes > Delete.
By unchecking and...