26 webservers and only two mongodb instances? Seems stacked.. Why not set up more instances and split the load across them (sharding, splitting collections across replica sets, etc) or similar?

Also - big question for me: were you using a ridiculously old version of mongo? I have yet to run into anyone who is on 2.0 or 1.8 and is still running master/slave (as opposed to replica sets). Sounds like your writes weren't working when you moved to replica sets because your client wasn't properly configured.