'You do not have access to the app' when trying to access heroku console

So just in case anyone is having a similar problem, this occurs because I was mixing the name of my Heroku Apps with the name of my git remotes. So when I was calling --app staging (the name of my remote), I should have been using the actual name of the app, as found in Heroku.

Be sure to run heroku login before using Heroku toolbelt commands for the first time. It will not tell you that you have not signed in before.