I'm wondering if your opinions on the difficulty of introducing new protocols have changed over the past decade. For example, Bittorrent has taken off, and while I used to have to manually configure ports on my NAT to allow Bittorrent to pass through, I no longer need to do so. Universal PnP seems to have taken care of that (at the cost of some security).
STUN/TURN/ICE have enabled NAT hole-punching to become fairly reliable, but the complexity involved is horrible. Try reading RFC 5245 and its companions - this isn't a sane way to design an Internet. It does work though.
New protocols are still an issue, but the problems differ depending on whether we're taking about the transport layer or the application layer. We've tried and largely failed to deploy alternatives to TCP and UDP. My effort, DCCP, for multimedia traffic is dead in the water due in part to NAT/Firewall traversal problems, and is now essentially tunneled over UDP. SCTP is successful in some limited circles, but you're very unlikely to see it end-to-end across the Internet for the same reasons.
At the application layer, it's somewhat easier. You can deploy new protocols over UDP, as BitTorrent did and as Google has done with QUIC, and they'll work in most places, but you'll still need a fallback. The universal fallback these days seems to be to tunnel over TLS on TCP port 443, because that's rarely blocked. The fact that we need to do this is an admission of failure on the part of the Internet architecture. The fact that it just about works is the reason we've not needed to address the underlying problem, which is the tension between security and extensibility.
