I poked around TreeSet and its interfaces for a while, and the best way I found to get the index of an element is:
set.headSet(element).size()
headSet(element) returns the sub-TreeSet of elements less than its argument, so the size of this set will be the index of the element in question. A strange solution indeed.