My wife is American and I am British and we both learned "it's not that big a deal" in school, but that was a long time ago. Which leads me to believe that it's not a UK-US thing, it's an age thing. The "of" has snuck into the language on both sides of the Atlantic over the past few decades. At first it was only in the spoken language but in recent years I have seen marketers and even journalists using "of." Language evolves, I guess.