Hello tizwaz -
Reboot PC. Ensure user is logging into the network successfully. You should run GWCheck (Analyze/Fix Databases) w/all options selected.
Next...
Update Your QuickFinder Index.
(From your server, get to your POA ---> F10 ---> Actions ---> QuickFinder ---> Update...)
If multiple people are having address book issues, the "Delete and Regenerate..." can really help. But I suggest the update for your situation.
You can also try to Sync the users account.
If you have my luck, (and I hope you don't) none of this will work, cause the user DID delete the entire list, and just don't wanna tell you. If that's the case, you'll need to look at restoring the user's database.
Either way, good luck.