A lot more than statutory law is at play here in the US: Court cases, regulations and states' implementations of the law matter greatly.
Basically, there's often a tacit (or even explicit) understanding that the winner of a bid to supply cable or Internet services to a municipal area will have the exclusive right to do so (mainly, the service providers argue, to make the capital investment involved in supply said services worth it).
There has been a long-running debate over whether or not last-mile networks and local cable are natural monopolies - i.e., whether or not it is most efficient for the industry to have a monopoly. If such services are public utilities with high capital costs, service providers might argue, they should have the exclusive rights to sales in an area.
In fact, it got so bad that the Supreme Court said that municipalities could be guilty of antitrust violations if they explicitly gave monopoly power to such providers (see Community Communications Co. v. City of Boulder).
So municipalities and service providers moved to implicit guarantees of monopoly - RFP processes that are hard for less-well-resourced companies to win, for example. [1] What I'd like to know is whether or not these implicit guarantees are still a problem.
Some states (like North Carolina) set up a 'franchising' process for service providers to get the right to serve an area. So it's not always just about permission from the municipality. It might be about whether or not your state's equivalent of a franchising process is exclusive on the local level. For cable, North Carolina's is supposedly non-exclusive, though I wonder how many times Time Warner runs into trouble getting approve to serve an area, and whether they end up developing small natural monopolies in some locations. But regardless of whether or not those monopolies develop, you have to think about who gets to run lines on whose land.
The fact is that the big companies have an easier time running lines for any data/media service (cable, Internet, etc) through easements and public areas. (This is the part some people refuse to believe. 'Oh, but anybody can purchase land!' Sure, but do you have the capital to do that, or does Time Warner?)
A truly competitive market would involve setting up the infrastructure and having the public own that, instead of owning or operating actual ISPs, which, to any rational observer, constitutes unfair competition, even in light of the desperate need for competition in some markets.
States and municipalities would hand out licenses to the infrastructure, not to the land. That'd be really cool, and possibly really efficient.
[1] - http://www.cato.org/pubs/pas/pa034.html (Good summary of the debate; pretty fair)