Ich habe jetzt noch etwas "herumgeforscht" und vermutlich die eigentliche Ursache für die o.g. Probleme gefunden. Vielleicht hilft es ja dem Einen oder Anderen.
Tuxedos Anpassungen beziehen sich primär auf zusätzliche Treiber, die eine bessere Kompatibilität der verbauten Hardware bedingen, als die vorhandene Standardsoftware. Das was mir hier in die Suppe gespuckt hat ist eine spezielle Bibliothek, die verwendet wird um erweiterte Funktionen zur Lüftersteuerung, HDMI-Ansprache und für spezielle Modi der Grafikhardware anzusprechen sowie verschiedene Leistungsarten der CPU einzustellen (Stromsparen, Vollgas usw.). Dazu hat Tuxedo ein Tool gebaut mit man das alles auf einer grafischen Oberfläche in verschiedenen Nutzerprofilen zusammenklicken kann und das diese Lib nutzt. Anscheinend verträgt sich diese aber nicht mit Kodi, so dass Kodi keine Videohardware erkennt und gleich zum Start die Segel streicht.
Schmeißt man nun dieses Tool samt der Bibliothek vom PC, dann rennt Kodi auch wunderbar. Das ist auch der Grund, warum mein alter Tuxedo-NUC ohne Probleme mit dem Tuxedo-Ubuntu lief. Der ist nämlich so alt, dass er die ganzen neuen Sonderfunktionen und damit auch das Steuer-Tool gar nicht hat. 
Weniger ist manchmal mehr. Ich werde die Daten noch mal bei Tuxedo in die Mailbox stopfen. Vielleicht haben die Jungs ja Lust das Problem irgendwann einmal anzugehen.