Sorry, I've been fried for the last few days...
You should try the following:
Go into the web admin
Select sqlCVS Diff from the Advanced Menu
scroll down to the QuickstartTemplate and QuickStartCategory tables in the DCE repository, check those...
Run the diff.
you should see your deletions... select them, and click revert.
See if this fixes your situation.