But it has to be a SortedSet.

Yes, I will not change that :-)
My point is that I think it is a Scala bug.
Minimized example

Welcome to Scala version 2.10.0-M4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_31).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.collection.immutable.SortedSet
import scala.collection.immutable.SortedSet

scala> class Foo(val name: String, val n: Int) {
     | override def equals(obj: Any): Boolean = obj match { case other: Foo => name == other.name; case _ => false }
     | override def hashCode = name.##
     | override def toString = "Foo(" + name + ", " + n + ")"
     | }
defined class Foo

scala> implicit val ordering: Ordering[Foo] = Ordering.fromLessThan[Foo] { (a, b) => a.name.compareTo(b.name) < 0 }
ordering: Ordering[Foo] = scala.math.Ordering$$anon$9@32370bf9

scala> SortedSet(new Foo("bar", 1)) + new Foo("bar", 2)
res0: scala.collection.immutable.SortedSet[Foo] = TreeSet(Foo(bar, 2))

and another example:

Welcome to Scala version 2.10.0-M4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_31).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.collection.immutable.TreeSet
import scala.collection.immutable.TreeSet

scala> import scala.collection.immutable.SortedSet
import scala.collection.immutable.SortedSet

scala> val s: SortedSet[String] = TreeSet()
s: scala.collection.immutable.SortedSet[String] = TreeSet()

scala> s + new String("foo")
res0: scala.collection.immutable.SortedSet[String] = TreeSet(foo)

scala> res0.head.hashCode
res1: Int = 101574

scala> System.identityHashCode(res0.head)
res2: Int = 1965496749

scala> System.identityHashCode(res0 + new String("foo"))
res3: Int = 856318696

scala> System.identityHashCode(res0 + new String("foo"))
res4: Int = 143836998

scala> System.identityHashCode((res0 + new String("foo")).head)
res5: Int = 1652856443

Created scala ticket: https://issues.scala-lang.org/browse/SI-5986

As workaround I have added new operators :+ and :++ by implicit conversion
Unfortunately this means that we must remember to use these until SI-5986 is fixed.
Is there a better way?

Updating tickets (#939, #940, #1941, #2213, #2214, #2215, #2219, #2222, #2223, #2239, #2240, #2249, #2250, #2252, #2253, #2254, #2256, #2259, #2263, #2264, #2265, #2267, #2270, #2271, #2275, #2277, #2286, #2287, #2289, #2290, #2303, #2304, #2308, #2310, #2311, #2317, #2323, #2331, #2374, #2392, #2405, #2423, #2425, #2440, #2444, #2445, #2453, #2456, #2459, #2473, #2477, #2491, #2495, #2523, #2534, #2541, #2544, #2545, #2549, #2582, #2583, #2589, #2626)

Updating tickets (#939, #940, #1941, #2081, #2126, #2213, #2214, #2215, #2219, #2222, #2223, #2239, #2240, #2249, #2250, #2252, #2253, #2254, #2256, #2259, #2263, #2264, #2265, #2267, #2270, #2271, #2275, #2277, #2286, #2287, #2289, #2290, #2303, #2304, #2308, #2310, #2311, #2317, #2323, #2331, #2374, #2392, #2394, #2405, #2408, #2423, #2424, #2425, #2440, #2444, #2445, #2449, #2453, #2456, #2459, #2461, #2473, #2477, #2485, #2491, #2495, #2498, #2501, #2505, #2515, #2517, #2523, #2534, #2541, #2544, #2545, #2549, #2582, #2583, #2588, #2589, #2598, #2599, #2618, #2623, #2626, #2627, #2630, #2631, #2633, #2634, #2635, #2637, #2638, #2642, #2643, #2646, #2647, #2648, #2649, #2650, #2653, #2655, #2657, #2658)