When I was around minotaurs relatively often a few months ago, I had a little trouble understanding them at first, but it quickly becomes quite easy. When an entire race has the same speech impediment, it isn't that hard to get used to. If you play a minotaur often, and especially if you converse with other minotaurs, I doubt you'll have much trouble understanding each other.

That is, unless the way they speak has changed since then.