Multiple pathing through a story is definitely a fun aspect to explore, and an ambitious idea to implement. While I'm not sure that "Mazredugin" managed the implementation quite so well as one might hope, I am still pleased by the effort.
The primary question to ask, when designing a game of this sort, is why these multiple paths exist at all. "Heroes", Sean Barrett's entry to IFcomp 2001, offered different perspectives and methods of solving the same story, based on the outlook and abilities of the various available player characters. "Mazredugin" seems to begin in the same way, but there does not appear to be very much difference between the characters in terms of what they are bringing to the table. Each character's "special ability" seems to be learned in-game rather than inherent to his character.
On the other hand, the point seems to be about getting these characters to work together and overcome their differences. In that respect, the lack of difference in skills and abilities could be forgiven; the lack could even be played up as a "we are not so different" moral. The characterisation differences still need to be played up, though. You can't present the similarities between characters as a fresh discovery unless they were obscured by the differences first. We need to see more of why the differences used to matter.
The design seems to support the idea of teaching co-operation: the first puzzle involves the player acting alone; the second involves the player acting in concert with the one character he chose earlier as the sort of person he likes the least; and the third puzzle involves all the characters each contributing one action towards the solution. It's a good beginning. I think it needs a little more thought.
The endgame is a bit of R&R, as the characters relax around a campfire and talk. There is a little of that "why the differences matter" here, which I found lacking earlier: in sharing, the characters give each other bits of advice to help out in those aspects of life that need it. I think this could have been a stronger scene if the differences had been better highlighted earlier. The walkthrough promised different endings based on actions in this scene, but I never found much difference. Perhaps I'm missing something here.
A breakfast sandwich: English muffin, sausage, egg and cheese. Everything comes together in the end, however you layer it. To be washed down with campfire coffee.