4GB? I have installed and run kubuntu on 2 different machines: 1GB memory and 2GB memory.
What version of Windows are you asking about? If you are going to run Kubuntu and Win XP, I would go with at least 512 MB. Although, more is better. My Kubuntu with all the bells and whistles runs 400MB to 900MB (my computer has 2GB total physical memory), depending on what I have running. XP can use less than this. 1 GB is probably good if you're going cheap.
Vista, however, can use a lot more. 1GB is kinda low, but will still work. If you're going to use Vista 2GB is better.
Like larryf215 said, DDR2 is pretty cheap, so give yourself a little breathing room as far as memory goes. Even if you're going with a cheap computer, don't scrimp on memory.