Automatic weights are not being computed as intended (Topology issue?)
It turns out the normals were not correctly oriented. When showing the normals in the editor, I saw this:



After recalculating normals (Ctrl+Shift+N, and unticking the "Inside" checkbox), automatic weights worked much better.