Did you perform the reset via iTunes? Chances are you reset it as a New Device... and not from your backup. That would explain why your contacts aren't there. The icon however... go into Settings>General>Reset>Reset Home Screen Layout... and see if your Contacts icon shows back up.