Need to restore from backup on iTunes, should've prompted you the minute you connect the new device and ask if you want to set a new phone on this account or restore from backup of "whatever you named your iphone"
Need to restore from backup... as long as you didn't name the new device the same as the old one, you should still be good even if you synced it...
Need to erase everything from the phone and restore from backup when iTunes prompts you