A couple things could have caused this:
Further update what probably happened was you entered an ion storm which made you use 50% of your power, at this time your oxygen was unpowered and led to your death when it was never given power again.
I got this achievement yesterday, and the difficulty is that it is relatively random. However, I'll share my anecdotal advice.
First, hit all the shops you can. Shops don't always have crew, but there's a chance that they might. I've found that shops in a sector belonging to a particular race tend to have that race more often, but it's random - sometimes I've been in Engi space and seen a shop full of Zoltans, for instance. Crewmembers tend to cost less than 100 scrap, but I'd suggest trying to have ~100-150 scrap on hand just in case you find a shop that's got 2 races you need.
One event that I believe is more common in "pirate" and "civilian" sectors is an encounter with a slaver. They may attempt to extort you to give them either some scrap or one of your crew members. If you fight instead, they may later attempt to surrender by offering you a crew member.
From time to time when fighting a ship and killing its crew, I've been told it was a prisoner transport ship and that one of the prisoners wanted to join me. I'd suggest attempting to take ships intact for this reason. I haven't seen any indications in the initial system event that would indicate whether a ship is likely to give a crewmember if taken intact, though.
There are also events where you find a lone survivor on a deserted station, and this can sometimes provide you with an additional crewmember. However, there's also a chance that they will go crazy and murder one of your existing crew, so this is not always a reliable way to make progress towards this achievement. Commenters have noted that having a level 2 medbay can counter this, as can a slug crewmember.
Best Answer
In the few times I've hired a mercenary for extra jumps it was when
Or
Or
And finally if you have one or more scrap arms the chance to turn 1 default rewards with bonuses into 2 default rewards with bonuses is quite enticing.
Most of the time though I agree with you, blast those mercenary scum into scrap!