1) Sync your phone with your computer and in iTunes make sure under your phone in the "Info" tab that your contacts are syncing to a program (outlook [express], window's address book, osx's address book, whatever).
2) Restore your phone
3) Sync your phone again and in iTunes under the "Info" tab, at the bottom of the screen, check the box that says "Contacts" under "Replace information on this iPhone"
Viola.