I don't know what people say when they say Patron warrior is "cheap". I might be biased cause I played it a lot, but I find there is plenty of strategy involved and it's quite fun.
I don't think it's cheap, as I think it's a very difficult deck to play well.
But I do think there are problems with it. First and foremost, its draw engine is too strong; it is entirely possible for a patron warrior to outdraw you by 10-15 cards, which is extreme.
But second and most importantly is the burst. It is quite possible for a Patron warrior to have 40+ damage in hand; that means they can one shot most classes even if the other player is keeping their board totally clear.
Take priest as a very simple example here: they can keep the Patron players' board entirely clear and keep themselves at 30 health, and even then they are under constant threat of dying in a single shot from 2x Frothings. This is what Blizzard refers to as "uninteractive."
One turn kill mechanics are generally frowned upon for this reason, but it's often held back by draw mechanics. The Patron Warrior's draw mechanics are so incredibly strong, however, that they can far more rapidly put the pieces together than a Malygos Mage, for instance.