None. It's a fallacy to believe a startup has to invariably solve a problem to go out there; companies like Foursquare or Zynga weren't solving much either.
People like to talk (tweet). People like others to listen to them talk (follow). People like validation (retweets, followers). People have short attention spans (140 chars). People like to be "in the know" (alternative to news source rss feed). People like to feel important (verified).
People will always be people. Twitter isn't a new idea. It just lets people be people.
When you read a newspaper (a thing of the past) you read headlines. If a headline catches your eye, you read the heading/intro, if you're still curious you read the article.
Twitter has allowed to converge all the headlines that might interest you into a single real time inbox, not only from newspapers but from whoever or whatever you're interested in. If there is more depth than a simple headline, there will usually be link to an article/video/photo/etc where you can dig into more info about that headline. It's the revolution of "NEWS" and everyone can broadcast or share/refer what they think it's "interesting".
Twitter solved the problem of dead-easy, publish-from-anywhere communication.
Restricting the length of a tweet solved the (perceived?) problem of having to say something meaningful in order to publish on the web. They removed many of the barriers to publishing and by virtue of getting a large user base solved the problem of reaching a large, captive audience for free.
More than anything, they solved the problem of there being no platform in existence that was adequately public, connected, and pointless enough to contain the terse, unsolicited musings of the modern human mind.
Ask someone you know how comfortable they are writing/reading an article(blog entry). Then ask them how comfortable they are writing/reading a sentence(Tweet).
Twitter helped deal with the problem of many people being uncomfortable with expressing themselves in longer forms of the written word. It also works for those with short attention spans. Combined with a following mechanism, that has proven very effective.
It allows people who go more in depth into things (i.e. writing long articles, producing complex content) to use the more shallow masses to broadcast (retweet, comment, like, follow) their stuff. So everyone can can participate.
Just replace "famous people" with people you care about. For example, I follow the tweets of several Firefox employees, the big names in various programming languages, my senators, etc. I do also follow some celebrities, but thinking that Twitter is Tom Cruise in the bathroom just makes you sound horribly out of touch.