I've "worked backwards" before too, and its disheartening as hell.
Whenever this has happened to me, I've just gone to my cleaning cartridges and started from scratch. Drain ink, fill cleaner, drain cleaner, fill ink... but I don't do this too often (twice in 5years) because it wastes a TON of ink.
I'm late into this post, so if you've already diagnosed a bad pump... then idk what to say, since I've never had a defective pump before *knocks on wood.
If anything, my best guess would be that... while you were servicing your magenta problem... the other heads sat exposed to air and clogged up too? Nozzle Wash/Custody Wash x99min.