Hallo,
wenn Du eh noch nicht viele Daten und so gespeichert hast, würde ich Dir den Tip geben, eine Distribution mit Abhängigkeitsauflösung empfehlen.
Du hast ja sowieso schon an Debian gedacht. Da macht im Moment der Ableger "Ubuntu" Karriere. Soll sehr einsteigerfreundlich sein. Falls Du KDE lieber magst, nimm "Kubuntu".
Ich selber kann Dir noch Mandriva empfehlen, damit habe ich angefangen und benutze es immer noch, auch wenn die letzte Version mit KDE 3.3 nicht auf dem neuesten Stand ist.
Gruß,
David