I’ve run into this problem a few times. I don’t know if it’s a minor bug or what, but sometimes parenting with automatic weights fails for no apparent reason. Fortunately the fix is easy:
First, the usual stuff. Make sure your mesh object doesn’t already have an armature modifier, make sure its scales and rotations are applied (ctrl-A in object mode. Do the same on the armature). You’ve already done this stuff in your file; I merely include it for the benefit of others. Put your armature in pose mode.
Now here’s the fix: put the mesh object in Edit Mode, select all, Ctrl-N to recalculate normals. Your normals are all fine already, but trust me.
Then pop back into Object mode, select the mesh, select a bone in the armature, hit Ctrl-P>Automatic Weights, and it works.
Why does correcting already correct normals solve this problem? Dunno.