I definitely mark the beginning of their decline as their transition away from KDE3. Several excellent, mature apps were either effectively killed (i.e. Konqueror) or neutered (i.e. Amarok). Lots of customizability (arguably KDE's key feature) disappeared, and for a long time, lots of core functionality was broken. This wouldn't have been as much of a problem had certain distros not decided to jump to KDE4 way too early in its life cycle leading to bad experiences for both new and existing users. I don't know if KDE ever recovered their previous momentum from that transition.
Sadly, I think the worst part about it was that the Gnome devs watched the whole thing and clearly learned nothing as seen by their Gnome 3 transition.