This post is for those who have a situation similar to the following:
  • Running Ubuntu 9.10-64bit as a guest in VirtualBox
    Native OS is Ubuntu 9.10-64bit
    Native hardware is Phenom series
    Experiencing performance issues such as random lagging
    CPU usage reports from within the VM are low despite lagging

Try diabling PAE/NX in the VirtualBox VM's config.