Of course, when there are millions of opportunities for coincidences to occur, and when coincidences are much more memorable than non-coincidences, the chances that everyone has a couple of these stories is pretty high.
It'd be interesting for someone to make a browser extension which logs all the ads you see, allowing trends over time to be spotted. It would also allow hard evidence in a situation like this.
Seeing a "Flaming Hot Cheetos" ad just could also just be the Cheetos is pushing this variety on their existing customers.