Here my 2 cent. The sorting is an issue and not pretty. I think this came up before. What you can do is the following:

1. Define an enumeration in the UI and save, but do not use it just yet.
2. In the process configuration source change the literal ID's to be unique and correctly lexicographic sorting.
3. Introduce a new attribute, editor presentation etc.
4. Rename the old attribute and editor presentation so you can tell.  (e.g. zzzz_do_not_use_old_Name)
5. Create a query, that finds all the work item by the same old value. Use the update multiple work items to set the new enumeration to the correct value, do this for all the values.
6. Retire the old stuff as good as possible and especially remove the old presentation