O seguinte trabalhou em 16.04 LTS: Eu corri os comandos abaixo
sudo add-apt-repository ppa:eivnaes/network-manager-sstp
sudo apt-get update
sudo apt-get install network-manager-sstp
sudo apt-get install sstp-client
Eu então abri as conexões de rede com
nm-connection-editor
e consegui configurar uma VPN a partir daí.