I believe I have solved my own problem.
The sub-categories that were adding the parent slug to the end were ones where I had identical tag names.
I deleted those tags, and then was able to go back into the category and update it successfully.
The Custom Permalink plugin also works now too.
I guess you can’t have identical category & tag names.