If they have "Edit Thread Title by self" and "Edit post by self" then users can definitely change the prefix from Thread Tools > Edit Title at the top right of the thread they started. Of course they must be within the time limit set for editing a post (make sure it's not set to 0 as they can never edit) to change the prefix.
If your users still can't do this then you'll need to analyse permissions for a user to see where the problem is.