KDE has never been illegal.
The GNU General Public License is a viral copyleft license. It's supposed to keep a wall between proprietary code and GPL licensed code, but there is a hole that allows part of a GPL'd application to be proprietary.
From the GPL:
However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.
This exception was originally added so that Emacs could run on Solaris and Windows. But as long as the proprietary object code is not distributed in the same tarball as the copylefted code, the GPL'd code can come with a notice: "This code runs on the operating system 'GNU/Linux plus libourproprietarystuff x.xx.', and libourproprietarystuff is included on this disc under the mere aggregation exception." It'll take a while for the courts to define "accompanies" so as to determine whether a distributor can mere aggregate GPL software with proprietary operating system software.