I eventually found that having a read only field on a template is what is preventing users from being able to change templates on documents. Is there a way to re-enable their ability to change templates regardless of read only fields?
We want the fields to be read only so that (as informational fields) they are not confused with fields that need to be interacted with. There was no intention of locking the fields to the document in any way.