Or am I missing something? Does decentralization mean something different in this regard?
There might be better implementations, but here's one which seems to work well enough:
diaspora* is a true network, with no central base. There are servers (called “pods”) all over the world, each containing the data of those users who have chosen to register with it. These pods communicate with each other seamlessly, so that you can register with any pod and communicate freely with your contacts, wherever they are on the network.
Most social networks are run from centralized servers owned and run by a corporation. These store all the private data of their users. This information can be lost or hacked, and like any system with a bottleneck, any problem at the central servers can make the whole network run very slowly, or not at all. It is also more easy for governments to “listen in.”
It apparently has over a million users, so if you're interested in the concept, this seems like a perfect starting point.