Unable to locate package virtualenv in ubuntu-13 on a virtual-machine

The Ubuntu package is called python-virtualenv, not "virtualenv".

Try This :

sudo apt-get install software-properties-common
sudo apt-add-repository universe
sudo apt-get update
sudo apt-get install virtualenv

It's also possible that you may not have run sudo apt-get update. It worked for me.