They do negogiate nationally. The problem with Comcast is that not all systems are equal so the local system has to decide what to carry (not sure if that decision is made locally or from headquarters). I know for a fact that the Comcast system in my locality cannot handle anywhere near the HD that the next jurisdiction over can handle. (Older, crappy SA system.)
Comcast was "built" mostly by buying local cable systems. Many of them failing financially. They are working to bring things up to date but it is taking years.
There are some other issues at play as well.... such as the Adelphia acquisition by Time Warner Cable and Comcast in 2008. That included rights to channels that e.g. Comcast or Time Warner did not have, or the other way around. They also re-consolidated their networks.
For instance, Los Angeles was roughly divided equally between Comcast, Adelphia, and Time Warner Cable, each having about one-third of the market, with about 5% on Charter. (I am leaving South-OC on Cox out of this completely). Time Warner got ALL of Comcast, ALL of Adelphia, and basically grew from roughly 30% to 90% overnight. In other cities, Time Warner Cable moved aside and Comcast took control of that market.
My mother-in-law was ex-Adelphia-now-TWC, and I was TWC. Channel lineups STILL have not changed from their Adelphia lineup standards, and she still has a Adelphia-branded Motorola DVR. Even now, there are differences in channel offerings. Not so much in actual different channels any more as more and more contracts expired, and have been re-negotiated for all the newly acquired (and lost) territories.
When all this went down, where there WERE difference between Comcast, Adelphia, and Time Warner, the now controlling company would not have automatically only put THEIR channels on.... channels Adelphia had, but TWC did not, had their contracts switched to TWC or Comcast, and the channels remained.
And indeed.... local markets have a say in things. Especially on the HD side, where they may not have the capacity for certain HD channels, or they don't have a feed setup. Where DirecTV receives all of their feeds by satellite in Los Angeles, (with a East Coast backup facility), each of the cable networks receive their feeds independently in each major market area. As such, the technology in each major market area needs to be there to receive them all. Additionally, there is some more technology that needs to be added for things like local commercial insertion, etc.
It has been this way since the dawn of cable.... in the beginning days of cable it was also about capacity, and many cable stations were more regional anyways. Analog cable had limited expansion, and it sometimes wasn't even possible to carry the newer stations, especially at the dawn of digital cable in the late 90ies, when new stations were launched, but could not be carried everywhere due to lack of digital cable.
TWC in Los Angeles is STILL a mess, dealing with the history from Comcast, Adelphia. And I would bet it is the same in cities where Comcast has to deal with history from TWC and Adelphia in a similar fashion.