The TreeSet orders it's elements. To do that it either needs a Comparator or if you don't provide one the element-class must implement the Comparable interface. You didn't provide a Comparator so the TreeSet casted the element to a comparable and that caused the Exception because your class didn't implement it.
Edit: reply to Ravi's question why it was only required for TreeSet
It isn't. You would have had the same error when using these objects in a TreeMap, or when they were in a List and you sorted it using Collections.sort(List). Actually, the latter would have given a compiler error since Java 5.0, but before it would have given the error.
Some structures or methods simply require Comparables. TreeSet and TreeMap use sorting for their internal storage. If you don't provide a Comparator then TreeSet / TreeMap assumes that the elements implement Comparable (see the Javadoc).
Collections.sort(List) has been able to prevent this using generics, but TreeSet / TreeMap couldn't. Removing any of the constructors was not an option as it would break older code. Making the generic element / key type bound on Comparable was also not an option because then it wouldn't be possible to create a TreeSet / TreeMap with non-Comparable objects using a Comparator.
If TreeSet / TreeMap could be changed completely, they should have no public constructors but factory methods instead (the constructors become private):
Apart from not being able to create a TreeSet without a Comparator, it would also give type inference:
Now about these two comments in my code. SortedSet / SortedMap are interfaces. That allows me to technically create a SortedSet implementing class which uses the system hash code for ordering. That would not require a comparator (so comparator() returns null) but the elements are still not Comparable. That would still be a possible type safety problem waiting to happen.
Hmmm. Perhaps my story / rant is a bit over complex for this discussion. Ah well