Armature parent with automatic weights swaps the legs
I applied the scale and rotation to the model before, so I guess the exact solution was to recalculate the normals. I'm not sure exactly, however applying loc,rot, scale and recalculating normals together fixed the issue.