Sorry, I wasn't around over the weekend.
Could you explain how they are editing the thread title? Is it from the node view (clicking edit) or through the thread view (thread tools), or some other way? As for the user changing the thread prefix later, that does sound like a permission issue.
Would you be willing to analyze one of your user's permissions and send me the breakdown so that I can set up the same test on my server?