Or the COLA calculations include many areas where you wouldn't want to live. Where I live now has a low COL according to the statistics, but that's only because it includes the poor areas nearby. The only place anyone would want to live is very expensive, and more than some of the bigger cities I've lived in.
Food prices vary greatly by region. Of the two cost calculators I referenced, one identifies Houston groceries as costing 45% less than Manhattan, and the other has a long list of representative food prices, many of which are around twice as much in NYC. This roughly matches my personal experience comparing Bay Area grocery prices to those in the Austin, TX region.
Same goes for cars — though less so for new cars, even there, when you check prices at a site like Edmunds, there are regional adjustments. For used cars, the same model/year/mileage combinations go for much less in Texas than California. And that's before transfer taxes and registration.
I haven't seen that much difference in basic food prices, at least not enough to account for the huge disparities in cost of living I've seen in calculators like these. I lived in Brooklyn for two months earlier this year and restaurants and little boutique organic foods shops were very expensive there were also big supermarkets that were pretty affordable. The only thing that was far more expensive than, Houston, for example, was rent.