What type of email account do you use?
Are they gone from the Contacts folder or just the address book?
Switch to the folder list so you can see all of the folders in your profile. Is there more than one contacts folder? (Ctrl+6 will take you to the folder list.)