256MB should be fine. Fedora includes KDE, but, from what I've heard, in a crippled form; as in a KDE that was once made to act a lot like Gnome, until they forgot about that goal in Fedora Core 4 or so.
Never tried Fedora. I've just used Ubuntu distros. All of that aside, I think that an OS should be able to run 256. If it can't then I think the OS is too excessive.
I agree with you PropellerHed. In the meantime I did some searching and got hold of few tricks to get the better of the RAM problem. Actually it seems they are loading too many processes which may not be required at all. So you have to manually stop few non required processes to get some memory back. I have also checked Ubuntu and if you ask me I feel it is better in terms of resource handling.