I think you're missing the package network-manager-sstp-gnome.
Here's what I did to make it work:
There's a PPA that provides precompiled packages for the necessary software. I added that with:
$ sudo add-apt-repository ppa:eivnaes/network-manager-sstp
...
$ sudo apt-get update
Then I installed the 3 packages like so:
$ sudo apt-get install sstp-client network-manager-sstp network-manager-sstp-gnome
I then rebooted but it should do to restart the network-manager service:
$ sudo service network-manager restart
After that you should be able to choose the SSTP option in the dialog where you can add a new connection. You can open that dialog with the command
$ nm-connection-editor
And then click the button that reads "Add".