(Sorted)MultiMap impossible for 2.8?

I'm trying to build a sorted multi-map. Unlike the the multi-map trait in
2.7, I need for methods like 'map' to handle the case of duplicate keys and
add them to the map (not just overwrite an existing Set at the key).

As a jumpstart I took the TreeMap and used it as a template for the
interface. I had to inline code from MapBuilder and
ImmutableSortedMapFactory to handle the case of 'B' becoming a 'Set[B]'. But
I'm now stuck with the few mutater methods -- the ones that are commented
out in the code is below (and also at http://paste.pocoo.org/show/148953/).

For example, from SortedMapLike we have:

override def updated [B1 >: B](key: A, value: B1): SortedMultiMap[A, B1]

I need something like:

override def updated [B1 >: Set[B]](key: A, value: B1):
SortedMultiMap[A, ??B1??]

But don't know how to get the return type correct. I've tried things like:

override def updated [B1 >: B, SB1 <: Set[B1]](key: A, value: SB1):
SortedMultiMap[A, B1]

This fails (at least) because adding the extra type parameter 'SB1' causes
the method to no longer override. I've tried all kinds of stuff, but am
quite stumped.

Any help would be greatly appreciated. I sure hope it turns out that it is
not impossible.

-----

package systeminsights.infra
package collection

import scala.collection
import collection.SortedMapLike
import collection.immutable.{MapLike, SortedMap}
import collection.mutable.{Builder}
import collection.generic.{CanBuildFrom}

//SMELL Had to copy this code from scala.collection.mutable.MapBuilder to
make B a Set[B]
class SortedMultiMapBuilder[A, B, Coll <: scala.collection.Map[A, Set[B]]
with scala.collection.MapLike[A, Set[B], Coll]] (empty: Coll)(implicit ord:
Ordering[A])
extends Builder[(A, Set[B]), Coll] {

protected var elems: Coll = empty

def +=(x: (A, Set[B])): this.type = {
elems = (elems + x).asInstanceOf[Coll]
// the cast is necessary because right now we cannot enforce
statically that
// for every map of type Coll, `+` yields again a Coll. With better
support
// for hk-types we might be able to enforce this in the future,
though.
this
}
def clear() { elems = empty }
def result: Coll = elems
}

//SMELL Had to copy/inline most of this code from
scala.collection.generic.ImmutableSortedMapFactory to make B a Set[B]
object SortedMultiMap {

def newBuilder[A, B](implicit ord: Ordering[A]): Builder[(A, Set[B]),
SortedMultiMap[A, B]] = new SortedMultiMapBuilder[A, B, SortedMultiMap[A,
B]](empty)(ord)
def empty[A, B](implicit ord: Ordering[A]): SortedMultiMap[A, B] = new
SortedMultiMap[A, B]
def apply[A, B](elems: (A, Set[B])*)(implicit ord: Ordering[A]):
SortedMultiMap[A, B] = (newBuilder[A, B](ord) ++= elems).result

class SortedMultiMapCanBuildFrom[A, B](implicit ord: Ordering[A]) extends
CanBuildFrom[SortedMultiMap[A, B], (A, Set[B]), SortedMultiMap[A, B]] {
def apply(from: SortedMultiMap[A, B]) = newBuilder[A, B]
def apply() = newBuilder[A, B]
}
implicit def canBuildFrom[A, B](implicit ord: Ordering[A]):
CanBuildFrom[SortedMultiMap[A, B], (A, Set[B]), SortedMultiMap[A, B]] = new
SortedMultiMapCanBuildFrom[A, B]
}

@serializable
class SortedMultiMap[A, B](implicit val ordering: Ordering[A])
extends SortedMap[A, Set[B]]
with SortedMapLike[A, Set[B], SortedMultiMap[A, B]]
with MapLike[A, Set[B], SortedMultiMap[A, B]] {

override protected[this] def newBuilder : Builder[(A, Set[B]),
SortedMultiMap[A, B]] =
SortedMultiMap.newBuilder[A, B](ordering)

override def empty: SortedMultiMap[A, B] = throw new
UnsupportedOperationException

override def get(key: A): Option[Set[B]] = throw new
UnsupportedOperationException
override def rangeImpl(from : Option[A], until : Option[A]):
SortedMultiMap[A,B] = throw new UnsupportedOperationException

override def firstKey = throw new UnsupportedOperationException
override def lastKey = throw new UnsupportedOperationException
override def compare(k0: A, k1: A): Int = throw new
UnsupportedOperationException

// override def updated [B1 >: B](key: A, value: B1): SortedMultiMap[A, B1]
= throw new UnsupportedOperationException
// override def + [B1 >: B] (kv: (A, B1)): SortedMultiMap[A, B1] = throw
new UnsupportedOperationException
// override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1)
*): SortedMultiMap[A, B1] = throw new UnsupportedOperationException

def - (key:A): SortedMultiMap[A, B] = throw new
UnsupportedOperationException

def iterator: Iterator[(A, Set[B])] = throw new
UnsupportedOperationException
override def toStream: Stream[(A, Set[B])] = throw new
UnsupportedOperationException
override def foreach[U](f : ((A, Set[B])) => U) = throw new
UnsupportedOperationException
}