Then it wasn't actually correct

Or, perhaps it was "correct" code but in the wrong event so it wasn't being executed when you thought it would/should be.
That means the record isn't actually being deleted. Why? Is the form bound to a query that includes a join to a second table? If so, the delete action works against the child table, not the parent table. You need to split into a form/subform.
The 3101 error can be caused in two situations that I am aware of.
1. The master/child links are not correctly set so Access isn't populating the FK for you.
2. Your subform is joined to the main form record (it shouldn't be) and instead of selecting the FK field from the child record, you selected the PK field from the parent record.
If you can isolate the forms and tables related to this issue in a separate database, we have a better shot at figuring out the problem.