This theory is trotted out every time that there is a discussion about cell phones or broadband in the US. Why do we not have incredible broadband for low prices in cities like Chicago and New York? Why did we not have great cell phone plans when regional plans were still prevalent?

It really helps to see the big picture to think, as you point out, about both mobile phone service AND broadband service. These are highly regulated services in the US that have terrible performance compared to the rest of the developed world, even only examining major cities.

Tokyo is one of the world's highest density places, with an average city block completely composed of an endless sea of highrise buildings that are made of very thick reinforced concrete. Radio waves cannot possibly travel very far in this place. Yet two of the main three carriers provide rock solid service. The third suffers from poor spectrum allocation (no spectrum in a range that penetrates thick material well). Recent regulatory changes have forced NTT (one of the two that has rock solid network everywhere) to resell access to its network to MVNOs at rates that are disclosed to the public, making an opening for tiny alternative carriers that are trying new service and pricing models.

Probably very difficult to dig up even a few feet of ground to lay new fiber, too, yet 100megabit ADSL and 100megabit fiber are available just about everywhere, in head to head competition. To improve competition the fiber pipe and network service provider are split (you pay NTT for the fiber, and one of about 10 different ISPs to push data down the pipe). AU is even pushing GIGABIT to select customers. Average 100megabit consumer pricing about $50 a month. Not to mention there is stiff competition for all this from wireless broadband from more providers than I can count (WiMax 40+ megabit, EMobile, Softbank, ...)

Japan's mobile phone pricing remains shockingly high, but the level of quality and competition in broadband service shows that the US could do much much better.

The population density argument is bunk. Why does ATT provide utter crap for cell service in NYC and SF?

Because they can and not enough customers will switch to competitors to make them care.

Probably because the places where you want to use your phone (inside buildings, in the subway) attenuate all radio signals.

This makes sense, -cell service on BART (one of the local subway systems) is spotty at best- but isn't the reason why. My ATT-using friends tell me that they have calls which get dropped or fail to connect while standing out-of-doors in public parks or on the street.

Here in Lisbon we have antennas inside the subway tunnels since 2006.

Note that I am not particularly competent in radio, but in those particular cases, wouldn't the geography (lots of hills around SF) and the prevalence of tall buildings (in the downtown cores of both cities) be a relevant concern?

Hills and buildings are a concern, but are a solved problem. :)

Let's ask folks who live in Berne or the hillier parts of Tokyo about the quality of their cell service. I bet it's far better than ATT users get in NYC or SF.