After digging around, I was able to find a couple of the categories in question. Checking the log files, I do not see that any categories were outright deleted. One (Young Cemetery) was renamed to the correct format, two others appeared to be duplicate categories, (John A. and John) and the last one has not yet been touched (Duncan).
I think what you have witnessed is a cleanup in progress. The categories you created were picked up by Category Error reports as they had no parents, and contained clearly duplicate information.
If there is a need to recreate categories associated with these cemeteries, please let me know and I can personally assist you to make sure they are done correctly.