You follow a canonical link to the resource, get a real page back, with real links, but js click handlers to enable AJAX-goosed speed for those with javascript enabled? And given that they imply a fallback for those times when javascript fails, aren't they actually better?
And GMail is a bit different than Twitter. It handles inward-facing data; content that no-one particularly wants crawled and wouldn't benefit much from caching.
Admittedly, you need a modern browser for that. But you can always present full-page-load HTML to users with older browsers and then provide AJAXy history-ified goodness to everyone else.
Twitter is very different. If you're signing in yourself to update your own feed, that's one thing. But when you are trying to view the feed of someone else, that's a horse of a different color.
The question really is: should Twitter be an "app" or a "site"? If you allow links in from the rest of the web, it should be a "site".
Unfortunately, web applications and web pages are growing increasingly divergent. It is simply not feasible to take the performance of web apps to the next level without doing away with full page loads. This is why Facebeook, Twitter et al are going the #! route. That's the cold hard truth.