Is the saying "It's not that big of a deal" incorrect? I would really like an answer to this as my children think it is correct.
English is mostly defined by usage rather than by reference to a fixed set of all-encompassing rules.
This means your kids are correct.
You might be able to make an argument about staleness of cliché.
I'd just say "wrong buster, it's a heck of a big deal in this household - thems our rules, suck it up."
Perhaps this Ngram will answer your question.
I am aware of the weaknesses of Ngram, but it works for rough-and-ready questions like this, and shows that "big a deal" is used more than "big of a deal", at least in writing.
Even though "big a deal" is the more used, I am not sure I would say your kids are wrong in any absolute way. The 'of' is pretty much redundant, and on a personal level I see unnecessary words as a barrier to clarity, but it is used widely in some areas.