Have you tried unmodified .htaccess file? I don't think you need RewriteBase /laravel/ line.

^I tried that as well but it does not seem to make any difference.

OK, after much banging the head against the wall and lurking on various sites for an answer, I found a solution:

        sudo chmod -R 777 /var/www/laravel/storage

The above permissions did the trick.

I still wonder though if there is anything that is not configured properly that might give me trouble down the road. Is there any definitive guide for running latest version of Laravel on Ubuntu+Apache?

Also, is there a better way to debug this type of errors in the future?