Unabled to Change Permalinks – Even Using the “Edit” (Resets to Original Permalink on “Update”)

Thank you TheDeadMedic, I should have tried this already, but here is the answer:

I had the “Slug” Meta-box hidden, using the “remove_meta_box” function because it is annoying, especially for users that aren’t tech-savvy.

Unfortunately, WordPress keeps the Permalink “Edit” as if you could edit it, but it is actually necessary for the “Slug” div to be on the page (even if it is hidden by “Screen Options”). Once I re-enabled the “Slug” div, it works again to change the permalinks.