diff --git a/xos/core/models/attic/xosbase_model.py b/xos/core/models/attic/xosbase_model.py
index 0250d77..5fea7c8 100644
--- a/xos/core/models/attic/xosbase_model.py
+++ b/xos/core/models/attic/xosbase_model.py
@@ -60,6 +60,10 @@
             with transaction.atomic():
                 for (k, models) in collector.data.items():
                     for model in models:
+                        if not hasattr(model, "deleted"):
+                            # Automatically generated through relations from ManyToMany fields do not have soft-delete
+                            # capability.
+                            continue
                         if model.deleted:
                             # in case it's already been deleted, don't delete again
                             continue
diff --git a/xos/xos_client/tests/orm_nodelabel.py b/xos/xos_client/tests/orm_nodelabel.py
index 89dd025..72d3069 100644
--- a/xos/xos_client/tests/orm_nodelabel.py
+++ b/xos/xos_client/tests/orm_nodelabel.py
@@ -29,7 +29,7 @@
 
 class TestORM(unittest.TestCase):
     def setUp(self):
-        self.test_node_label_1_name = TEST_NODE_LABEL_1_NAME + "_" + ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(10))
+        self.test_node_label_1_name = TEST_NODE_LABEL_1_NAME
 
         nodes1 = orm.Node.objects.filter(name="test_node_1")
         if nodes1:
@@ -46,21 +46,17 @@
             self.node2.save()
 
     def tearDown(self):
-        # TODO: Deleting NodeLabel seems to be broken -- appears to be a cascade failure
-        # attaching a nodelabel to a node causes deleting the node to also be broken.
+        node_labels1 = orm.NodeLabel.objects.filter(name=self.test_node_label_1_name)
+        for node_label in node_labels1:
+            node_label.delete()
 
+        nodes1 = orm.Node.objects.filter(name="test_node_1")
+        for node in nodes1:
+            node.delete()
 
-        #node_labels1 = orm.NodeLabel.objects.filter(name=self.test_node_label_1_name)
-        #for node_label in node_labels1:
-        #    node_label.delete()
-
-        #nodes1 = orm.Node.objects.filter(name="test_node_1")
-        #for node in nodes1:
-        #    node.delete()
-
-        #nodes2 = orm.Node.objects.filter(name="test_node_2")
-        #for node in nodes2:
-        #    node.delete()
+        nodes2 = orm.Node.objects.filter(name="test_node_2")
+        for node in nodes2:
+            node.delete()
 
         pass