I can only get Ubuntu 16.04 on my system (macos ~2010 running latest OS) if I first install 14.04 and then upgrade it.
I'm using the latest version of VirtualBox for Mac. It seems to be limited to ubuntu flavors. I've tried ubuntu, xubuntu and ubuntu-gnome. Latest Kali installs fine (which is debian based).
Here's what I get when I first boot up from ISO: