A while back, I did an experiment trying to prove that while Twitter links are marked as nofollow, that they actually ARE followed.
I had a registered, but never-used domain. Google searches for the domain name yielded zero results. I published a simple, static HTML page (no possibility of trackbacks/pinging/RSS/etc.), and tweeted a link from a public Twitter account (the published link was nofollowed). Within 16 hours, the page was picked up and indexed.
This alone tells us multiple things:
Links on Twitter accounts can be followed, regardless of the link state. I’m sure that some spammy accounts are “sandboxed” and not followed, but for the sake of discussion, we’re referring to good accounts.
The next logical step here is to push for a self-hosted short URL service. Even though most services (like bit.ly) do 301-redirects, it’s better for it to redirect from your own domain.
Links from good Twitter accounts are a probable ranking metric.
My personal Twitter account currently has a SEOMoz Page Authority of 58. That’s pretty respectable. So, it’s not crazy to assume some of that will get passed (Google did crawl the link, after all). If nothing else, it’s a great way to get a site indexed quickly!