今、工事がどの段階なのかにもよると思うけど、どちらにしても接着剤を使っているだろうからそれを剥がすのはかなり大変。下地の合板もはがれたり剥がしきれなかったりで床が凸凹になるよ。そうならないように努力はするだろうけれど。そのまま上に貼るっていう手もあるけれど、階段とかドアなど各所納まりを考える必要がある。
一度冷静になって考えてみて、どうしても我慢ならないかどうか考えてみよう。まーこれでも有りかもってことなら他に少しサービス工事などお願いしてフローリングはそのままにしてもらい気持ちを納得させるという方法もある。どうしても我慢ならない場合は強引に直してもらう方が精神的に良い場合はあるけれど、何か他の弊害が出る可能性があることは覚悟しておいた方が良いかもしれない。

ほぼ　タンドリー氏の言っていることで正解だと思います。

私は、別の見地から・・・

>全面違う色の床材を張られてしまい困っております。

これですが、どういう経緯でのことでしょう？
※「カタログ」で決定した色柄を指定し、張ったがイメージと違った。
あるいは、こうなるだろうと想像したものと違った。などなど・・・
これであれば、施工者は「うん」とは言わないでしょう。
カタログの色は「印刷」の色で、必ずしも同じにはなりません。
写真で撮ったイメージ画像などなら、光の当たり具合により変わります。
張り替えになったして、恐らくお気に入りの床材は、探し出せないかもしれません。
※現物見本を取り寄せ、それを指定し、品番も同じものだったが、いざできあがると見本と違う。
これも、現物見本と言いながら、「製造ロット」が変われば、あるいは天然物であるがゆえに、違ってしまうことはある事です。
※選んだ、指定した品番と別物が納品され、施工された。
これであれば、「なんとしても張り替えねばならない」と、主張されれば施工者としては、断れない事例でしょう。ただし、タンドリー氏の言うように、施工に伴う弊害と、天秤にかけても張り替えると言うのならです。私もあまりお勧めできない工事ですし、施工者との相談をおすすめします。

> とは、どの程度求めるのが妥当だと思いますか。

それはあなた様が納得するのが一番だけれど、今後の付き合いもあるしね。

> 張り替えに掛かる金額分の減額を求めたら、非常識でしょうか。

それもあり得ると思うし、向こうのミスならしょうがないと思えばそうだけど、当初の予定はそういった金額もかからない予定だったわけで、お互い気持ちよく間を取るのが良いのかなと思うけれど。

引き継ぎミスは100%向こうのミスはミスなんだけれど、極端な言い方をすると、一度決めた事項をお客様のわがままを聞いて何とか変更を受け入れてくれた、わがままを聞いてくれた部分は善良に感じるし、現場側の人間としては物事がコロコロ変更になったり、ギリギリに決まることは仕事が増えるだけではなく本当に混乱の元だからね〜、そういう部分は労いながらあなたの納得点をうまく見出すのがいいんじゃないかと。全然違う色ではなくて、一度は自分で選んだ色なんだろうから。その会社のやり方とか、図面の回し方にもよるけれど、最終的な図面や仕様書の確認などはないのかな？そういうのを確認して依頼をするのは相互の義務だと思うけれど。

>とは、どの程度求めるのが妥当だと思いますか。

一応、何かやってほしかったけど、あきらめた。とか、とりあえず後回しにしていたとかの、ことってありますか？「それを提案してみる」ということも一つ。
何を。ということは、無いんだけど・・・・というなら、
業者に、「何か、サービスする。ということではいかが？」のように提案すると、
何かしらの提案が帰ってくるのでは？
それらで、お互いに納得できるか？できないか？　が、実際、妥当なところではないでしょうか？
私たちの方では、それを値踏みもできないし、推定することも無理かと存じます。　

>張り替えに掛かる金額分の減額を求めたら、非常識でしょうか。

その判断も、無理なことかと存じます。
お互いの気持ちの問題ですからね。
若い方々のことばで言う、「げきおこ！」って言うのなら、当然そのくらい！って、思うでしょうし、あのときちょっと、無理言っちゃったし・・・みたいな負い目を感じることがあったというのなら、遠慮気味の提案だろうし。
　くれぐれも、冷静にことを運ぶことを、おすすめしておきます。