I disagree with most people. I think, the part about patron warrior that pushes it to such heights of strength are the card draw mechanics. We saw the same with miracle rogue, still being strong after leeroy and only finally being laid to rest after auctioneer nerf.
Short aside- Oil rogue, just in case someone who isn't all that familiar with the deck, is very different from miracle especially since it does have to fight for board and is way way less reliant on huge finishers (although definitely capable of it due to prep + oil synergy).
What makes a combo deck really work? Getting all the combo pieces! What enables that? Card draw! What is the draw engine for patron warrior? Battle Rage!
This sleeper card is responsible (imo) for patron warrior being what the deck has become in the right hands:
When Patron warrior hits it out of the park, often times I've seen, it is because the card draw can be crazy in combination with patron warrior, acolyte, etc.. Double acolyte into whirlwind can easily draw 2 cards off acolyte from damage, and then 2 additional cards off battle rage (+1 if hero is damaged), so you end up drawing 5 or more cards (more if more board was in place already). At that point your opponent has like 1-2 turns to kill the warrior, because the combo is likely to take them out the next turn.
Kripp is right in pointing out that warsong commander + frothing existed before. Patron warrior definitely transformed it from a kinda once in a while grand slam into a consistent power house slugger. I think there are multiple ways to approach nerfing it, without killing it off. It isn't like UT nerf stopped midrange/face hunters, nor did UTH nerf, nor did buzzard nerf. These decks thrive in different yet still viable forms.