Auch wenn dieser Fehler nach dem Tastaturtausch unwahrscheinlich ist, zunächst die triviale Frage: Die Tasten Strg, Alt, Entf für sich funktionieren aber schon?
Evtl. läuft irgendeine Software (AUTO-Programm, ACCessory, Virus), die sich in die Tastaturbehandlung einklinkt? Was passiert, wenn Du nur den Rechner startest, ohne eventuelle Festplatte und ohne eine Diskette im Laufwerk, sodass garantiert nichts geladen wird? Funktioniert Ctrl-Alt-Del dann?