Sitecore publishing service is not running error

After spinning up the new Publishing Service for Sitecore 8.2 I noticed that publishing was not working and the following error was appearing on the publishing dashboard.

The publishing service is not running. Please contact your system administrator.

This error is generally caused when Sitecore is unable to connect to the publishing service itself. You should ensure that you can access it in the browser and are able to see "{“status”:0}" - which means it's working okay. Also check the PublishingServiceUrlRoot inside the show config admin page to ensure it points correctly to the service URL.