It seems as if it is a software issue. Not a loss of data. If you had backed up your phone or contacts with desktop manager, try reloading the backup onto the phone and then see if it works. If not, then the easy route would be to stop at the tech dept. In the carrier's store. Was this after a download or app install?
in the address book hit menu filter see if you have it filtered with check mark uncheck it should bring back contacts. i did this once by mistake
check that out for possible reason now the error message I have never seen that.