How about charging users?. Like monthly plans etc.
edit: The service was/is App.net, and it was founded by Dalton Caldwell. It used to make the rounds on HN all the time.
Or they could offer little widgets you can buy and post on your profile page, like LiveJournal does (assuming it still does; it's been ages.)
Or a combination of the two, like DeviantArt.
There's plenty of options. Hell, sell Twitter plushies. That failwhale image was pretty cute.