My wife's Droid had this problem. It would randomly decide to lose all her contacts. She had the backup option checked in settings, but they would not reappear. On her phone, what we figured out is the phone would sometimes delete all her contacts. Going online to check out her contacts (on Verizon), we would find all her contacts in the deleted folder (trash bin). We would check them all and restore them back to the contacts folder online... and the phone would automatically update with the contacts.