After upgrading to 3.1 while developing a new theme, I had an issue where the Admin Bar did not display correctly. At first, the problem was that the drop-down menus did not drop down and the search bar appeared below the rest of the Admin Bar.
After a little debugging, I discovered that the issue was with the default styling of lists that was applied by my stylesheets. For me, the specific problem was that I had set overflow:hidden to prevent a rendering bug where bullet points/numbers are not correctly aligned (it's a common issue). Setting overflow:inherit for #wpadminbar ul & #wpadminbar ol fixed the problem.
While debugging, I also ran into problems where the menu bar was totally blank. As I recall, that issue had to do with the position property.