Well, it fixed it by itself. I went to the Verizon store to tell the guy what I was experiencing. Clicked contacts and BAM...all of my contacts and more. All of my existing contacts plus every contact I have in my facebook that has a phone number listed in their profile.
He said that it should just fix itself, if not turn the phone off and remove battery, reinstall battery, turn on.
It took about 45min to 1 hour after I took out the battery to notice the changes. Was that the fix? I don't know. But it is back to normal, and then some.