512M means you'll have a maximum of 256M per virtual machine (plus the space parallels itself takes in RAM). Given how RAM-hungry OS-X is, I would highly recommend that you go to at least a Gigabyte, maybe 1.5 (I've 1 GB and am contemplating up'ing to 2 myself).
Cheers...