Some pretty good ideas already but thought I'd throw my own experience in the mix. I have some pretty old laptops (2004 vintage) that have 512MB RAM 20GB HDD Pentium III and P-IV processors.
Distros: Kubuntu 10.x was challenging but ran. Part of this was due to KDE4 (see Desktops below) which has vastly improved over time so I should probably give it another go with Kubuntu (latest).
Ubuntu 9.x-10.x (GNOME) doesn't run well -- locks up a lot.
Linux Mint: A little better but not with GNOME. Xfce or KDE only.
Linux Mint Debian: GNOME = no go. (see Desktops) Even tried Xfce but couldn't get it to run right. Finally converted over to KDE but still a no go. Almost anything "GNOME"ish was too much of a challenge.
Debian "Lenny" (KDE 3.5): No problems whatsoever.
Debian "Squeeze" (KDE 4): Only recently has this run well.
Aptosid (KDE 4): No problems with Sidux (predecessor). Had some issues when the name changed to Aptosid but this might have been more due to the changes in KDE 4 than to Aptosid itself.
Desktops: I haven't tried GNOME 3 or Unity.
GNOME 2.x just became unusable. (Bloat?) Did not dare use any Compiz or any other 'special' features.
KDE 3.5 ran (and runs) fine but without special features.
KDE 4 ran, then didn't, now runs fine.
Xfce: Runs great most of the time if part of the original installation (Xubuntu, for instance). With the exception of Xubuntu 10.x (didn't keep it long enough to troubleshoot) I haven't had problems with a default install.
After having had problems with GNOME (v2) and searching for solutions, then loading KDE on a lark, I have come to prefer KDE as my Desktop Environment. Purely personal preference. I haven't tried GNOME 3 yet but I should (and soon).
Debian Stable is just that, stable. Usually rock-solid but certainly not the bleeding edge. Fedora does offer more of the bleeding edge but as purely personal preference, I prefer Debian's arrangement, package management, and command structure (I came from RedHat to Debian via SuSE and Debian immediately felt more natural to me than the other two (or three: slackware)).
Aptosid and Mepis (both KDE, note my bias) are both wonderful derivations of Debian that seem to run well on old hardware as well as provide more of a bleeding edge. Linux Mint runs fine as well when installing KDE. I really like the Linux Mint Debian concept but GNOME and my old hardware do not get along and I wasn't (smart enough?) able to get it converted to KDE well enough to keep it.
Now that I have a newer laptop (running Wubi/Kubuntu 10.04) I might start trying out some of the newer Desktop Environments like GNOME 3 or Unity. But until I have the time to devote to switching this box over, I will just run Wubi on this and Debian/Aptosid on the older boxes.