Você estava realmente muito perto:
$ sudo apt-get install python3-pip
Quando você diz que pip3 funciona, tenho certeza que é o pip da versão mais recente do Python3. Você pode fazer pip3 --version ?
Isso também deve ajudar: link