I tested the most recent version of this plugin with WP 3.1.2, and it showed my tweets just fine.
However i was busy working on a CSS file, uploading this a number of times and refreshing the page in IE, and it stopped showing tweets.
(i.e. "No public twitter messages").
Disabling and re-enabling the widget fixed this.
http://wordpress.org/extend/plugins/wp-twitter-sidebar-widget/
