Pacote não disponível após a instalação bem-sucedida com o apt-get ou pip

Estou tentando instalar algumas bibliotecas nas minhas máquinas Ubuntu. Tome esta biblioteca como exemplo - virtualenv

ubuntu@ip-172-31-44-172:~$ sudo apt install virtualenv
Reading package lists... Done
Building dependency tree... 50%
Building dependency tree       
Reading state information... Done
virtualenv is already the newest version (15.0.1+ds-3ubuntu1).
The following package was automatically installed and is no longer required:
  libllvm4.0
Use 'sudo apt autoremove' to remove it.
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
ubuntu@ip-172-31-44-172:~$ 

Mas agora, quando tento usar o virtualenv, recebo -

ubuntu@ip-172-31-44-172:~$ virtualenv
The program 'virtualenv' is currently not installed. You can install it by typing:
sudo apt install virtualenv

Mesmo para a biblioteca 'pip3'

ubuntu@ip-172-31-44-172:~$ sudo apt install python3-pip
Reading package lists... Done
Building dependency tree       
Reading state information... Done
python3-pip is already the newest version (8.1.1-2ubuntu0.4).
The following package was automatically installed and is no longer required:
  libllvm4.0
Use 'sudo apt autoremove' to remove it.
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
ubuntu@ip-172-31-44-172:~$

ubuntu@ip-172-31-44-172:~$ pip3
The program 'pip3' is currently not installed. You can install it by typing:
sudo apt install python3-pip

Qual é o problema aqui?

Corrigi isso desinstalando e reinstalando todas as bibliotecas acima

sudo apt-get purge virtualenv
sudo apt-get purge python3-pip

e depois reinstalei estes novamente. O problema que eu acho que poderia ser - mudei da minha versão python padrão de 2.7 para 3.5.