The reason why your primary is now no longer primary is because you have to have enough votes to form a majority in a replica set - in your case that means 2/3 minimum. With your specific failure that doesn't seem to make sense, but imagine instead that the primary in question had instead become isolated from the 2 secondaries (a network event for example). In that case you would not want two primaries elected, so instead it would step down until it could see the other set members.
In order to get the primary back to working you need to do one of two things:
- Get the other set members back up
- Reconfigure the set so that a majority can be formed (add more members, go to a single)
See here for more information on the reconfiguration option:
http://www.mongodb.org/display/DOCS/Reconfiguring+a+replica+set+when+members+are+down
Basically, your replica set will failover, but you have to have enough members to actually do an election.
In terms of why the secondaries died, I can't say based on the information you have provided here, but I can tell you that it's not because they were too stale. A secondary that falls too far behind will report as being stale but will keep running (and voting for the primary) even in that state, until you fix it and bring it back up to date. See here for how to remedy a stale set member:
http://www.mongodb.org/display/DOCS/Resyncing+a+Very+Stale+Replica+Set+Member
