1) Create a new TreeMap and switch the Keys and Values from the old TreeMap. In pseudocode:
2) Create a List from the Set returned by entrySet() and use Collections.sort() and a custom Comparator to sort the Map.Entries in this List.
I'm not sure which I prefer. I've implemented #2 previously and it can get messy. If the values already implement Comparable then #1 seems cleaner. Otherwise, you will need a custom Comparator there as well.