It seems that to get Elasticsearch to run on 16.04 you have to set START_DAEMON to true on /etc/default/elasticsearch. It comes commented out by default, and uncommenting it makes Elasticsearch start again just fine.
Be sure to use systemctl restart instead of just start because the service is started right after installation, and apparently there's some socket/pidfile/something that systemd keeps that must be released before being able to start the service again --- I didn't bother to track that down, feel free to look for it 
Here's a sample Vagrantfile for it:
Vagrant.configure(2) do |config|
config.vm.box = 'ubuntu/xenial64'
config.vm.provision 'shell', inline: <<-SHELL
sudo apt-get update
sudo apt-get install elasticsearch -y
sudo sed -i 's/#START_DAEMON/START_DAEMON/' /etc/default/elasticsearch
sudo systemctl restart elasticsearch
systemctl status elasticsearch
SHELL
end