Hallo Oli,
Recht haben und Recht bekommen sind zwei paar Schuhe, aber lassen wir das...

Der Händler bei dem das Auto gekauft wurde und die Werkstatt die die Kats nachgerüstet hat sind zwei unterschiedliche Personen, richtig!?!
Dann sieht´s folgendermaßen aus:
Oli gegen Händler: Wenn der Händler nicht zugesichert hat, das der Wagen mit Katalysatoren ausgestattet ist, dann ist das auch so lange kein Mangel, wie der Käufer hätte erwarten können, das eine derartige Ausstattung "die Regel" ist. Ich meine, Du kaufts einen 2000´er Polo, der keinen Kat hat. Darüber würde man sich sehr wundern; bei einem 87´er JXS sieht das schon anders aus.
Oli gegen Werkstatt: Du hats mit der Werkstatt vereinbart, das sie Dir zwei Kats einbauen. Das haben die, wie Du beschrieben hast, auch ordnungsgemäß getan. Durch den Einbau ist nachweislich (hoffe ich zumindest) ein Schaden entstanden. Früher sprach man von der sog. PVV Positiven Vertragsverletzung, heute regelt das BGB Deine Rechte explizit. Lange Rede; kurzer Sinn: Die Werkstatt muss den Schaden beheben, und zwar auf ihre Kosten, wenn seit dem Einbau der Kats noch keine 2 Jahre vergangen sind. Dabei bleibt es ihr überlassen, ob sie die Maschine selbst überholt, oder einen ganz neuen Motor einbaut.
Scheue nicht davor, einen Gutachter einzuschalten, der feststellen kann, das die Überhitzung durch falsche Fühler bzw Thermostate verursacht wurde.
Im Streifall muss die Werkstatt übrigens nachweisen, das der Hitzeschaden nicht durch ihr falsches Handeln verursacht wurde.
Ich würde diesbezüglich aber auch nicht bei 123recht erkundigen, sondern mir einen Anwalt nehmen. Wo wir uns hier bewegen, ist simples Vertragsrecht und Handwerkszeug eines jeden Advokaten (sollte es zumindest)
Good luck!
Christian