I had the same problems you described with deleting categories/links ... what I ended up doing is going into the dbcats.cgi manually and getting rid of the old categories.
However, this is a *bug* that Allen does need to tackle. (Sorry, Allen!)
Donate to UBBDev today to help aid in Operational, Server and Script Maintenance, and Development costs.
Please also see our parent organization VNC Web Services if you're in the need of a new UBB.threads Install or Upgrade, Site/Server Migrations, or Security and Coding Services.