It could also autocomplete based on who just tweeted to you. I guess there's only so far that you need to take these things, and twitter was designed to have a simple interface.
Complex autocomplete logic doesn't have to make it any less simple in it's interface. I had a greasemonkey prototype that autocompleted on friends, followers, googled usernames etc and sorted on relevance given current timeline/replies. And non-intrusive if you want to ignore.
Edit: It should definitely autocomplete based on who you're following, but pg wasn't yet following anyone when he sent his first tweet.