Restore the phone with iTunes, when starting up (after asking about location services and others) it offers to start from scratch, start from backups on iCloud, or start from backups on iTunes. Select iTunes, plug in your phone, select back up, and done.
----------
Did you transfer your contacts into iCloud? If so, all you gotta do is sign in with your iCloud account.