自己解決できました。
synchronizedのメソッドにあるスレッドが入ると、そのオブジェクトのsynchronized メソッドの全てが待たされるみたいですね。

ttp://ideone.com/6Smmp
コンストラクタを少し修正しました。
249行目のSortedMapを元にして、コンストラクトする処理ですが、最中にSortedMapが更新されないとも限りません。
SortedMapをインタフェースに使う時点で、この問題を回避することは出来ないと考えて間違いないでしょうか？★
(呼び出し側で、引数にするMapを同期させる必要がある。)

あともうひとつ。
クラス内のメソッドを全てsynchronizedにする魔法の文言ってないでしょうか？★
アスペクト指向じゃないと無理ですか？