512 MB is plenty for most Linux apps. In fact, one of my old Pentium II laptops has only 192 but runs Mandriva 2008 just fine (although the 3D desktop would be out of question for processor speed reasons, not memory). I actually seem to have more free memory with this latest 2.6.22 kernel.
Meant to add that the Pentium II laptop has a 4 GB drive so is very comparable to the Eee with its solid state disk, but only about half as fast.