I had the same problem -- there were 2 things I needed to do.
From: https://devcenter.heroku.com/articles/heroku-cli
I needed to install the new Toolbelt. Instructions are included on that link, and are platform dependent, so I won't include them here. The other thing I needed to do, which I didn't realize at first after installing the toolbelt, was to make sure the heroku binary that was running was the one installed by the toolbelt.
if you run which heroku, it is supposed to return
/usr/local/bin/heroku
If it doesn't, you will need to remove the other binary, or change your path. In my case, I needed to do a gem uninstall heroku in addition to installing the toolbelt, then everything worked.