I had a little trouble running Ubuntu server on VirtualBox today.
Thankfully the answer was easily found at Installing Ubuntu 8.04 server on VirtualBox « {S.A.Z.W.Q.A}.
All you need to do to get Ubuntu server firing up is to open the settings screen for your virtual machine, and then tick the Enable PAE/NX box.
Click OK and fire it up! No problem.