After synchronising with Google, all contacts that have phone numbers associated with them disappeared.
I tried to enter a new contact just to test this. If I sync again the new entry disappears as well. How can it be recovered?
My phone is a Galaxy Note II
Did you clear Contacts Storage?
Settings > Applications > General Applications > All (at the top) > Contacts Storage > force stop > clear data
then Bring up "Contacts" you will then see "You don't have any contacts to display" > press Menu button > Accounts > choose account to sync (your gmail account) > Sync
Google can restore your contacts from the last thirty days.xc2xa0 This is for your desktop computer, and would probably propagate into your Android as well, if Android is not fixed after fixing your desktop contacts, fix those on Android with our other answers, afterwards.
Google search:xc2xa0 lost gmail contacts
Ensure "contacts to display" is set to "all contacts" (under the settings in your contacts app). This ensures you will see contacts from your Google account.
It would he good to validate your Google Contacts data by going to http://www.google.com/contacts. Verifying that all the data is there confirms that the issue is with your phone's display, not the data.