Yes, they are grammatically correct.
While I wouldn't call it common, it's not at all obscure a construction. Making them up off the top of my head:
(After seeing the HR department stuffing pink slips in envelopes, the layoffs were) not that much (of) a surprise.
(Being told she looked like his mother was) not that charming (of) a compliment.
("Buy five get one free" is) not that much (of) a discount.
(And it's) not that great (of) a deal (either).
(He's) not that fluent (of) an English speaker.
(He's a fine programmer, but he's) not that much (of) a sys admin.
(emacs is a fine operating system, but it's) not that great (of) a text editor.
(After last season's use of the fashion, it's) not that fresh (of) an idea.
In almost all cases, it's used to connote disappointment. It's a way of saying that something did not meet a standard, particularly one that seems self-evidently pertinent because it has to do with proposition of what the thing is in the first place: an inadequate sale can barely be said to be a sale at all. If I can get a can of peas at store X for $0.50, the fact that store Y has them 20% off their regular price of $1.00, i.e. $0.80, will make me think, "Well, store Y, I suppose it is technically a sale, but I'm having trouble going along with your proposition that it's a sale to the point of thinking of it as one, because the savings of this sale are so inadequate to compete with store X that, it's not that much of a sale."
It's only very slightly informal, but I can't think of a way to use the expression of disappointment in something (which this almost always is, unless used ironically) that doesn't risk offending someone. You'll want to be careful using it, constraining yourself to employing where you really do mean to let someone know that something is inadequate, and when you're prepared for the sort of reaction that can provoke.
Interestingly, you have the classic exception at the top of your list: "Not that big of a deal", which is used to reassure that something hasn't given offense or caused distress.