Looking at Savage Species page 28, the Minotaur is a fine, balanced monster to play, that will alter be able to go the route i would have taken any way - Reaping Mauler, and a devastating grappler to aid the party! I am really happy with the way the Minotaur progression looks in the SS book, let me know if you will change things, because in that case i might decide to go with something else. I like that it gets fighter BAB, two good saves, good ability bonuses and Large size.
Story: He is a young but already developed representative of his race, that has been captured by slavers several years ago, after he had roamed out of his clan's underground labyrinth in search of adventure in the world above.
He had spent some time being displayed as a curiosity in a traveling menagerie, but was later sold to a gladiator arena in Thay. There, he fought unarmed most of the time, due to the tendancy of nobles paying the arena master to enter staged fights and "win" against inexperienced monsters that lack equipment.
Just prior to the start of the adventure, however, a young nobleborn lad had decided to face the Minotaur with nothing but a rapier and leather armor, and prove his worth to a lady in the audience. Things did not turn out so well, when the young human lost the grip on his weapon as he stuck it in the thick muscular arm of his attacker, and was promptly impaled trough the eye on the minotaur's horn, and then torn apart in a guresome display of battle rage and strength. The victorious gladiator was quickly subdued and almost beaten to death, after which he was sent to await his execution in the prison.