I have a Celeron 500 (all most 6 year old) and a Semperon 2400+ (less than $300 el-special, ASRock mobo, Semperon 2400+, 512ram, 80gb hdd, DVD burner, 350W case ) and they do well with any thing that I threw at it. (both have 512 megs ram)
Debian is a nice start if you are comfortable with reading because the install interface is quite dated, however it will become second nature to you after a few installs. SimplyMepis (KDE defaut) is quite a polish Debian variant that you might want to take a look at (very nice GUI install interface), and I heard Ubuntu (Gnome default) is another nice one to try.
Fedora, Mandrake, and SuSE (Yast - IMHO, it the best install/control console) are also nice to try because their GUI install interface is just as good or better than MS.
You can expect minor glitches with Xconfig with most Linux distro, but it wouldn't take much to iron out.
IMHO, you should download a few distros and spend a few weeks install & getting familiar with it to find out which distro you like best. You might endup dualboot/or more distro till you find one that you are most comfortable with.
Good luck!
[Edit] It just dawn on me why I like SuSe 9.2, because Yast reminded me of my brief but good experience with Netware 5-6 years ago.