Você tentou o que a documentação do Laravel diz?
Permissions
Laravel requires one set of permissions to be configured - folders within app/storage require write access by the web server.
Portanto, se você estiver usando o apache com o mod_php, os diretórios e arquivos dentro deste caminho devem pertencer ao usuário do Apache (geralmente www-data, apache ou httpd dependendo da sua distribuição). Se você estiver usando PHP via fastcgi, php-fpm etc., os diretórios e arquivos neste caminho devem pertencer ao usuário que está executando o PHP para este vhost.