Well it may be due to the amount of contacts. Have you made sure that you have a the latest version of google on the phone? If you have not yet run updates, it may need that to connect you. Also, you may wish to (which should have been done before the reset) check from a computer to see that the contacts are actually in your google account. If you don't have a computer, try logging in through the phones browser instead of the app. This way you can see what you would from a pc (mostly). Make sure the contacts are there. If they are, then make sure the account is set to sync to the device. It may well not be. If it isn't then set it up to sync and then sync your phone. You should have the contacts.
Also, make sure the phone is not set to...