I guess Linux doesn't work with everything
 

I'd been told that Linux is so robust it'll run on anything even an old 386. Have this old Compaq Presario 5000 that wouldn't accept several Linux distros. Did install Kubuntu 7.04 OK. Installed and configured the Nvidia graphics card and updated everything but it just didn't run very well. Even though it had 384 megs of ram, it was sluggish and would just freeze up. Finally gave up and reinstalled XP Pro and it runs great. When I think about it, just about every desktop machine made has been made for Windows. Linux has the difficult job of trying to work around this other OS.

Linux will indeed run on just about anything, even an old 386. But the big graphical desktop environments like KDE and Gnome won't. They require too much memory and processing power. Your system will probably work much better with a lighter window manager. Xubuntu (Xfce) would do you better than Kubuntu.

Or try a distro like Puppy or Damn Small Linux instead. They're specially designed to be lightweight for low-powered systems.

Tried Puppy and DSL. They are definitely small and nibble but they lack the whole Windowesk experience of Gnome and KDE. Did try a distro called Slax which was a stripped down version of KDE. Very fast and stable but it's author didn't want it to be installed. Just run as a live CD.

With really old hardware windows98 lite or nano is the fastest.

Puppy, DSL and the like are nice if you only use the pc for certain tasks. As soon as you have to install 3'rd party packages you are entering compatibility hell.

There is absolutely no doubt that gnome or kde are not a good choice for less than 512mb ram, and I wouldn't have expected anything else. What you want is XFCE, but with a popular distribution. Something like Xubuntu (Which is really still Ubuntu), or I think Fedora lets you choose XFCE during installation... In addition you can choose more lightweight Programs (Look at DSL and Puppy as a reference - you can get all their programs for Ubuntu too)

If that is still too slow, you can look into something like fluxbox. Unfortunately I don't know any popular distribution that does offer an already set up lightweight fluxbox environment. Fluxbuntu is in the making, but as for now it's still not up to it.

You should give slackware a try, I have it running on a p3 with 256 mb of ram with KDE and it runs fast

But that's because of the version of KDE it's running, and not because Slackware is so much faster, no?
I have never tried slackware, but I think you are expected to know a thing or two about linux before you start using it.
The reason why I usually recommend ubuntu, is quite simply its forum and www.ubuntuguide.org.
Fedora has something very similar with fedorafaq.org. Those two cover almost everything that a new user will come across.

Slackware 12 runs KDE v3.5.7 and if you start off with slackware then you learn alot faster then ubuntu or fedora

oohmygod...
I just read a little about slackware. Are you kidding me? No package manager... Yes you will learn faster, but you will learn stuff that you never needed in the first place, unless you were going to build your own distribution some day I guess. And what do I learn by resolving dependencies manually?

All I need to know is how to do what I want to do, right.

You know, I've been using Slack for over ten years and I've never had to "manually resolve" a dependency. Now, before everybody jumps on the old band-wagon let me just say I don't recommend Slack to anyone who isn't serious about learning the "guts" of Linux. Back to the dependency thing - It never comes up when you either, use only the packages that come with the distro, or build things yourself. I guess you mean figuring out what the requirements are for a particular program. I usually just read the docs that come in the source of most programs. I will admit that there are some exceptions, but that seems to be happening less and less frequently. As for the act of manually resolving dependencies; all you do is type and then go get any libs you may not have. Like I said, I've never had to do it.

there is a package manager, it just doesn't resolve dependencies for you. You will learn stuff that you would use on any linux system and its not that hard actually, Slackware is simple, straightforward, fast and no bloat

I have a PIII, 733MHz 160 mb SDRAM, which runs PCLinuxOS pretty quickly, and it uses KDE.
Mepis 6.5 is also decent on this system.

True, but that is because you have no choice. I've been using Linux since 2002, and I do not recommend Slackware to anyone new to Linux. Learning because you are ready is almost always better than learning because you are forced to.

Try Austrumi. Its based on Slackware, very small and fast. You have to change to English though when you start up.

Since nobody else has mentioned it, I'll throw Zenwalk into the suggestion list (technically, it's basically a minimal Slackware install.) I've got it running quite happily on an old Compaq laptop with 256MB ram. I use it mainly for Internet access, and have no problems running Firefox, Thunderbird, and GAIM at the same time. I found the install to be pretty painless, assuming you know something about the hardware you've got. I highly recommend it for older equipment.