The problem with twitter as it currently stands is that it relies on a centralised server (well, servers). That's easy to block, or legally compel to remove content. Imagine instead that every user on twitter had their own "stream" replicated on both their own computer and those of all of their followers. If you choose to follow someone, you get access to their stream either directly from the person themselves, or any of their other followers.
This would partition the system according to popularity. The more followed a person is, the more replicas of their tweet stream available. When someone retweets something, it appears in their own stream, so retweets benefit from this replication. Any tweets that are particularly important and popular would be virtually impossible to suppress.
To prove that tweets had originated from a particular user, every user would have a public/private key pair generated when they first begin using the system, and all tweets would carry an associated cryptographic signature. "Registering" for the system would be a matter of generating an identity using a key pair and a username. Clashes and impersonation of usernames is something I haven't yet thought of a solution to, though usernames would be for display purposes only; the real identity would be the public key.
Replica discovery is another challenge, but there's much in the existing P2P literature and practice (esp bittorrent) that could possibly be of help here.
As far as business models are concerned, Twitter's current one wouldn't work, as it relies on the centralised nature of the system. However it would be possible for developers of individual clients to make money by providing various value-adds, and these could co-exist with open source clients.
Thoughts?
Side note: There seems to be a bug in the comments system where the last paragraph is omitted. Is anyone else experiencing this?
Extra last paragraph