Para seu PC atual, com 256MB de RAM, tem que ser o Xubuntu, ou então outra distro mesmo, como o Debian Lenny com KDE 3.5 ou XFCE. Depois de instalar o Xubuntu, se achar que está lento, podes instalar o LXDE pelos repositórios pelo comando sudo apt-get install lxde e ter um pouco de paciência para configurar este ambiente.
Quanto ao seu PC novo, ele virá com o Megalinux, que é baseado no Ubuntu 8.04. Se você não gostar dele, é melhor recomeçar do zero. Ainda mais que existe algum risco de o Megalinux ser ruim que nem o Fenix.