We're using Python + Twisted for our XMPP servers at HipChat (http://www.hipchat.com) and neither have let us down. Hopefully we can reach 500k+ connections on such a small number of servers as well.
One specific note about Twisted/Python vs node.js: The combination of Python's yield and Twisted's defer.inlineCallbacks generator makes it really easy to write and maintain nonblocking code. In node I find it far too easy to get lost in a sea of callback functions. Here's what you get to do in Twisted: http://enthusiasm.cozy.org/archives/2009/03/python-twisteds-...
As a side-note, this is why I love the software engineering community: everyone's always so willing to share knowledge and help each other out. Let's hope we never lose that as a community!
Whatever language you choose though there's plenty of interesting scaling problems to work on ;)
That said, Tornado is a really neat piece of software, and it worked very well for FriendFeed and others. It really just came down to personal preference.
Do you need to make async calls to the database because your queries are slow?
Yeah, the documentation is awful. Fortunately I've pretty much always just assumed that all documentation is going to be bad, so I pretty much never even bother trying - I just read the source.
I wrote justin.tv's chat backend, in Python, using the Twisted network libraries. It has scaled to peaks of more than half a million concurrent chat connections, on 8 fairly modest commodity servers. Python is more than capable here, with the right networking approach. Feel free to ask me anything about it.