I had the same thing happen when I upgraded to 6.1.2 recently. My daughter and I are both on the same plan with the same apple ID. I lost all my own contacts and gained all hers. I took my phone into Apple, who couldn't help me, and then to Verizon, who could. Verizon was able to delete hers and restore my contacts to the point when I started using the iPhone, but I lost the last 1.5 years of added contacts. Apple really needs to work this bug out. What an enormous pain.
Good luck with yours.
Naturalla, let's make sure that your contacts are restored. Have you tried Elector's step of signing into iCloud? Have your contacts been restored? Make sure that iCloud is set to backup your contacts. Go to Settings, iCloud and ensure contacts are set to On.
When you originally synced your contacts to your phone, did you use VZ Contact Transfer? If the contacts haven't been backed up to My Verizon in over 30 days, that may be why they are no longer on the site. Please attempt VZ Contact Transfer just in case to see if any contacts transfer over http://vz.to/V8QSbZ.
Let me know if you need further assistance.
Follow us on Twitter @VZWSupport