Next september we are going to initiate usability tests with dotlrn within communities of practice and e-learning program for a group of people in the corporate sector. We have similar programs running with other groups and not rare we are facing the necessity to develop easier interfaces to make dotlrn accessible to a growing diversity of users.
I think you pointed a great weakness in dotlrn interface. Our experience have been showing us that tab structure really create a false sense to users and frequently people feel very discomfortable with their experience with this structure. People claims too there are links that could be immediatly acessible from tab structure instead buried in the interface.
I tried Selva-theme today in a test installation and i think it represents a good approach to improve the quality of dotLRN associated to usability issues. I made some screeshots and uploaded them to http://www.teknedigital.com.br/screenshots/ . I did little modifications to Jeremys' code to get header_logo change working and putting Selva Theme as a option for portal template layout. The idea about submenu structure is really interesting and will be a great enhancing to dotlrn interface when fully implemented.
Our approach to usability tests will follow heuristic evaluation methodology developed by Nielsen and modified for an evaluation of e-learning programs by Reeves et all (see for example http://dl.aace.org/10405).
We are not totally committed with this approach yet but we have a number of papers published here in Brazil using Reeves' approach and some of them could be used in our work. I really appreciate if you could put available documentation developed by Dorian and others.