I had the same problem. The contacts were all there, I just couldn't see them. I knew because all my texts had names, not numbers. And I could type in a name and it would recognize it.
I think re-syncing is the best solution. That fixed my music and videos and so on. But there is a shortcut that worked for me until I could re-sync. Go to Settings -> Mail, Contact, Calendars. Scroll down to the Contacts section and click on your name in My Info. That brought up my full contact list. And they stayed even after exiting. Everything was fine after that.