分かった

ジェネリック関数を定義するばあいには引数に互換性がないと困るようです。
on lispにもそんな感じの事が載っていました。

CLOSは名前が同じ全てのメソッドの引数リストが合同でなければならないと要求する．引数リストが合同なのは，同数の必須引数とオプショナル引数を持ち，さらに&restと&keyの用法に互換性がある場合だ．異なるメソッドが受け付ける実際のキーワード引数は必ずしも同じでなくともよいが， defgenericによって全てのメソッドが最低限受け付けるキーワード引数の集合を定めることもできる．

さっきの例は、&restと&keyの用法に互換性がないということになるのかな。

Practical Common Lispをさらに読むと納得できました。引用は面倒なので割愛します。要は「defmethodで利用できる引数は、defgenericにて指定した引数と互換がなければならない」ということらしいです。

defgenericを明示的に実行していない場合は、最初のdefmethodをもとに自動的にdefgenericが動作していると考えられます。

エラーが発生する例の場合は、最初のdefmethodには、&keyだけが利用されているので、defgenericには&keyしか指定されていない状態となるのかな。

順番を逆にした場合には、最初のdefmethodには&restだけが利用されているので、defgenericには&restのみが使われる事になるはずです。そして、&keyはdefgenericに指定されてない物をdefmethodで利用することは出来る仕様らしいです。このため先ほどの順番では上手く動作するようですね。

defgenericで&restと&keyを両方最初に書いてから使えば良いという訳ですね。
さらに言うならdefgenericにはとりあえず&rest書いておくと楽なのかもしれませんね。