I had success the first time by recreating the Categories. Most Contacts regained their previous associations. Unfortunately I did not note the order in which I recreated the Categories.
I suspect the data file (Contacts) still has a link (broken) to the deleted table (Categories). Once the table (Categories) is recreated the links become "live". However if the table is recreated in a different order (Categories created in an order different from original), the wrong Category will be associated with the Contact.
eg. Category 1 = Family Category 2 = Business Category 3 = Unfiled
I never was able to identify the case for the glitch. I suspect a Microsoft update may have affected the function of the Desktop database. This suspicion is based from upon other database user experiences.
This has just occured to me again a couple days ago - with more serious issues (lost entries). No success this time as recreated associations appear to be completely random.