The field name is gender_id
not gender
.
For a bit of history and explanation:
The contact api automatically takes a few fields (notably gender_id, prefix_id, suffix_id, state_province_id and a few others) and gives you the label as well as the id for convenience. However this is not consistent across all apis and is not something I would generally rely on.
In v4.4 a lot of work was done to standardize option lists and the upshot is that 'create' type actions will now accept either the id or the name of any option (not the translated label).
So civicrm_api3('contact', 'create', ['id'=>123, 'gender'=>'Male'])
and civicrm_api3('contact', 'create', ['id'=>123, 'gender'=>2])
will do the same thing.
Come to think of it, it would be nice to accept either 'gender' or 'gender_id' since that's more consistent with the output. Here's a PR for that.