A versão padrão do sistema é aquela apontada pelo link simbólico /usr/bin/python . Em 16.04 isso deve ser python2.7 , mas você o alterou (como você descobriu, isso é uma má idéia, pois muitos programas no Ubuntu usam Python e não funcionarão se encontrarem a versão errada), e está apontando para /usr/bin/python3 que é um link simbólico apontando para /usr/bin/python3.5
Remova o link simbólico que você alterou (você não pode simplesmente sobrescrevê-lo em uma etapa):
sudo rm /usr/bin/python
e faça um novo symlink com o mesmo nome para a versão correta do Python (que originalmente apontava). No seu caso, isso é python2.7 , então:
sudo ln -s /usr/bin/python2.7 /usr/bin/python
agora python --version lhe dará Python 2.7.12 (ou 2.7. [algum número] dependendo de qual versão secundária está instalada)