This side note by @Sludge solved my problem. I had all the appropriate permissions in the main AndroidManifest.xml but not in the debug AndroidManifest.xml.

I'll ask the developers of the permission_handler package if they can please specify which AndroidManifest.xml is the culprit.

Just a side note: There are different AndroidManifest.xml files in your project (...src/debug, ...src/profile, and ...src/main). Adding the permissions to the main version described above should work but if you're noticing inconsistent behavior make sure you're putting all of your permissions in the same AndroidManifest file.

Many thanks, @Sludge