‘An error occurred in the upload. Please try again later.’ for users with different roles

Oh, well, while writing the question I tried to copy the full link that takes the ajax call: example.com/wp-admin/async-upload.php and noticed that for the subscibers it was taking the user to their account page while the admins where getting The link you followed has expired. Notice on the screen. And then I got the ‘Aha’ moment – I was restricting no-admins from wp-admin and redirected them to their account page. After removing this redirect it all worked.