Same situation here, different error message:
Sorry, login failed. Error message from Twitter: This method requires authentication
Oddly, the login isn’t *really* failing. My tweets were being displayed in the sidebar I configured for Twitter Tools just fine. However, tweets were not being sent when I posted to the blog. I’ve been having the problem for a month or more, on a 2.5.? version of WP, and now 2.7
