Actually, twitter should not have any google indexing problem. Search engines have provided new scheme for indexing hashbang URLs with Ajax content[1]. But, maybe, not all search engines have implemented it yet.

If I had to guess, primary reason would be that server is blind as to what page needs to be loaded when you click twitter.com/#!something and an ajax request actually serves the relevant content, so it's relatively slower. Twitter's implementation was particularly slower.

[1]https://developers.google.com/webmasters/ajax-crawling/docs/...