The second, much more important problem: discovery. This is the only user-focused service Twitter actually provides (the ability to find the accounts you want to follow). The 'network effects' people love to throw out as excuses for using shitty services like Facebook is not as big a deal as people around here pretend. Email works just fine and there's no 'network effect' preventing me from running my own mail server. Discovery is so important that just about everyone reading this post would rather have a lock on discovery (and the accordant ad revenue) than promote any kind of federated system. Discovery is search, and search is hard, and searching across a federated service is damn-near impossible, which is why there's no email whitepages any more. Much simpler (and more profitable) to hash everyone's email addresses, or let them pick a cute username -- whatever, so long as you hold the keys and can sell ad space on the results pages.
Nothing like what you're describing is possible any more. There are no more federated open standards; the IETF is merely propped up to rubberstamp whatever Google or Microsoft wants to do next.
I would like to add the spam problem to your explanation. A distributed system needs a distributed solution for spam, which is much harder.
But we also need to add a little complexity to the description. There is a difference between decentralized and distributed systems, with email the former and usenet or irc the latter.
Both discoverability and search are trivial with distributed systems, but also offers the possibility of competing networks. It is interesting to note that the open protocols actually faired worse in those cases, as it lends itself to competititon, and a someone with access to deep pockets can leverage that against you.
If more developers acknowledged possibilities of semantic web (or "Linked Data" approach as it been re-branded) not just for reducing entropy of the web, but also to provide solid services for ordinary users, it wouldn't be so hard to develop critical mass to be widely used.
So do we really need new technologies like GNU Social/Twister to accomplish this, or can we just repackage the above tools to look like facebook/twitter/g+/ello, and have decentralized social platforms. The biggest hurdle I can imagine is non technical users not knowing what in the hell to do with an XML page when trying to follow a person, so I'd propose that a new link type similar to <a href=emailto:address> be established -- perhaps something like <a href=follow:myfeed.xml> -- which would open the feed in the follower's default RSS reader. And I could sort my feed into circles/groups, which are really just folders in a feed. I think this could be prettied up to look the same as and be just about as easy as twitter, with no new technologies needed. A service could host each of these components, and thus look just like a full social network as we've come to know them.
The fact that it's so often referred to as "microblogging" makes me wonder why this sort of set up isn't discussed more often (unless I'm missing it). It would also then be trivial to host your own, because really all you'd be doing is hosting a blog, and using an RSS reader. It seems so obvious to me that I feel like I might be overlooking something.
[0] https://www.facebook.com/help/224049364288051