$5 a month would be totally worth it for a lot of people. Even with promoted tweets, etc., I think people would go for it.

Charge, but let people do whatever they want with their own data ... give them access to their full history of their own tweets and maybe some other advanced features. Meanwhile let everyone use twitter.com for free if they want.