I really agree with Patrick on this (well put, nice analogy!). A key point depends on what you think a theme could or should be capable of affecting.
The way I see Moodle is there are 3 critical parts
Usability / user experience (most critically navigation)
Appearance (although emotional engagement is part of this, and I feel an important part as you want to engage users with high quality visual design, appearance also overlaps with usability as things like layout, visual weighting, typography etc have a big impact).
I have found using themes frustrating because they feel hard to use / restrictive. Changing colours is nice (but pretty low on my list of priorities as it has less signifcant impact on user experience than othere aspects of Moodle). I would rather have more control of
a) the layout
b) the modules themselves
For example with the course menu so far I have been unable to make the order of the courses non-alphabetical for users (although logging in as admin the order is the same as set through the admin area!). So I cannot solve this through themes.
Hopefully Tim's work will result in a more coherent and usable navigation mechanism.
So for me while I place navigation as a higher priority than themes I still think that themes can mean more than just changing colours.