By the rules in the new MM and DMG, those monsters should have been:
CR: 4 (base for minotaur) + 5 (for five levels in an associated class) = 9
The party should receive 4 X the eperience for 1 CR 9 creature. For a 9th level party, that would be 10,800 total. This is the same experience that the PCs would get for a CR 13 encounter, btw.
The ECL should be: 13 (4 CR 9 monsters).
It should have been challenging for a 13th level party of 4 characters with average stats and equipment. At least one PC should have been threatened in some way. It should have cost this party some significant portion (20 - 30%) of their resources.
It should have been very difficult for a 9th to 12th level party of 4 characters with average stats and average equipment. These PCs should have been pushed to their limits by this encounter. There should have been a very real chance of a PC death. When you have a very real chance of death combined with 5 crits in 6 attack rolls, you get a PC death.
The party should receive treasure for an ECL 13 encounter. In addition, the minotaurs should each be outfitted with equipment equivalent to the equipment appropriate for a 5th level NPC fighter. The DMG lists this (on page 117) as full plate armor, heavy steel shield, mwk melee, mwk ranged and 2150 gold worth of coins, gems, jewlerry and precious items. The equipment of an NPC is part of the NPC's challenge rating.
*********************
Unofficially, the DM should have run a mock battle before putting the PCs up against this foe. CRs, ECLs, etc ... are just a rouh starting point. Individual party strengths and weaknesses can drastically change the difficulty of a battle.
For instance, pretend you have a party of 4 wizards. Now, set them up against a beholder. A challenging fight to say the least.
Now, replace those wizards with four ranger archers with a favored enemy of beholder. The rangers should have an easier time against this foe.
Same CR. Same EL. Different challenge.
I run almost all of my battles in mock format when I write the adventure. I check to make sure that the battle is as difficult as it is supposed to be. In many cases, I change the CR to account for strengths and weaknesses of the party. Remember: you're not giving experience for monsters. You're giving experience for the party beating a challenge. You need to balance the experience granted against the difficulty of the challenge (which is effected by the abilities of the PCs), not against the strengths of the monsters (which is independent of the PCs).