When you create the symlink with php artisan storage:link command it contains the full absolute path to the storage/app/public folder. So, the solution is create a symlink with a relative path from the project root like:
ln -s ../storage/app/public public/storage
===OR===
From inside public_html run:
$ chown -R username:group storage
Of course replace username:group with the same username:group combo that you find against any other public file or folder when you run ls -l whilst in the public folder.