Using the freely available online tool, I plotted the frequency of you're welcome over the last 200 years:
Then I plotted the frequency of no problem over the last 200 years:
There's no doubt that no problem has increased in frequency, but its rise started 50+ years ago and it has dwarfed you're welcome since the 1970s.
Just for kicks, I performed searches on Google and Bing. Here are the results:
However, these data are hard to tease apart because no problem can be used in a wider variety of contexts than you're welcome, so it's to be expected that its frequency is greater. But the dramatic and sudden rise of the phrase in ALL contexts 50 years ago is the truly interesting fact, imho. I have no explanation for that. One of Seitz' friends suggested that the influence of Romance language speakers (e.g., Spanish speakers in North America) has led to the semantic/conceptual borrowing of de nada. A nice thought, but it would take much more research to confirm/deny such a thing.
This does give some credence to half of Seitz' claim (if not his complaint) as yes, indeed, the frequency of no problem has increased. However, there's no indication that the frequency of you're welcome has declined; quite the contrary. Its frequency has held solidly over 1.5/mil since the 1960s and hit its all time high just last decade. According to his IMDB profile, Seitz was born in 1968, which means his entire life has been lived well within the boundary of the roaring no problem period. Exactly when did he experience the golden era of you're welcome? And how can it be said that no problem is REPLACING you're welcome if you're welcome is as strong as ever?
This is probably an example of the yester year phenomenon whereby history is rewritten because a person assumes the days of his youth were the greatest days on Earth; therefore they must conform to his current beliefs about what the greatest days must be like; therefore the past was different than it really was.
*FYI, the sources for COHA are Fiction, Magazine, Newspaper, and Non-Fiction Books.