Wordpress - Can't upload media, permissions are correct

I found the problem. In settings > media the folder for uploads was actually pointing to a different path. Once I redirected it to wp-content/uploads it all worked.

If you moved your page from one host to another - check if your Upload path is correct to your new host (and not a leftover from previous host)

Navigate to: http://YOURDOMAIN/wp-admin/options.php