How to get Laravel 5 working on Heroku?

I figured it out. With the new Laravel update to 5.1.4 some extra security has been added. This means that a 16 char appkey no longer works. As many have found out editing app.php in Config helps.

config/app.php

 'key' => env('APP_KEY', 'SomeRandomStringSomeRandomString'),

'SomeRandomStringSomeRandomString' actually allows the app to run. This is a 32 char key, which is the new minimum. Hopefully this helps everyone. I know I ran into a lot of frustration when my previous methods no longer worked.

Also note, this means that you are on a environment without its own appkey. Probably will want to generate a new 32char key for security.

Following on from your answer, this appears to be the correct way to set up your application key locally. Firstly, ensure your environment file exists in the root of the project:

cp .env.example .env

Then set encryption keys inside the app:

php artisan key:generate

For non-development installations, you will probably want to set this environment variable (and any others, such as database connection strings) in your Apache vhost instead:

SetEnv APP_KEY SomeRandomStringSomeRandomString