Don't bother installing VirtualBox on a machine with anything less than 2GB of RAM. VMWare Player 3.5 is still downloadable, and works great with older systems. It will run with up to 75% of your physical memory, whereas VirtualBox will not allow you to use more than half. This will let you install Fedora 16 which needs 786MB to install, even LXDE or XFCE. After installation I turned it back down to 512MB.
Otherwise VirtualBox is awesome on new-ish boxes. I have it on my Dell Core 2 Duo (cerca 2007) with 2GB running Ubuntu 12.04LTS.