A couple of problems I ran into with these upgrade steps, which I solved, were:

1. If sudo apt-get update fails to find dokku repository information
   see https://github.com/dokku/dokku/issues/3397
   then fix this with
   wget -qO - https://packagecloud.io/dokku/dokku/gpgkey | sudo apt-key add -
   then run apt-get update again and it should now cleanly complete.

2. If you have any apps that are “not deployed”, the dokku ps:rebuildall will fail. Not deployed means an app has been created but never pushed to with any code. To fix this, remove the unused app with dokku apps:destroy YOURAPP or if you don’t want to do that, simply run dokku ps:rebuild YOUAPP1, dokku ps:rebuild YOURAPP2 etc. on each app you previously stopped. Rebuilding installs all dependencies from scratch and starts up the app.

The Accepted Answer is only half the answer. The problem I found with the one-click Dokku droplet for Ubuntu 16.04 is that the the source URL for Dokku in the dokku.list isn’t correct and therefor wasn’t getting the newest versions of Dokku, herokuish, sshcommand and plugn.

To fix this:

1. ssh into your droplet
2. Edit the dokku.list sudo nano /etc/apt/sources.list.d/dokku.list
3. Change xenial to trusty and save

dokku.list should look like this:
deb https://packagecloud.io/dokku/dokku/ubuntu/ trusty main

Once done, follow the recommend updating from Dokku:

sudo apt-get update
dokku apps
dokku ps:stop APP # repeat to shut down each running app
sudo apt-get install -qq -y dokku herokuish sshcommand plugn
dokku ps:rebuildall # rebuilds all applications