We currently have two mechanisms to classify messages, one being flag/star, one being tags. I believe we should merge them to one unified mechanism, at least from the user's POV. The flag/star could grow into being just another tag, even if it might be special-cased for IMAP storage (I heard flagging is a standard IMAP technique while tags aren't). We currently have a threadpane column for the flag/star status, we possibly could extend that to tags in general, maybe with a possibility to assign icons to tags or such, and with a single mouse click on the column possibly bringing up a dropdown menu with tags to select - I'm just creating ideas as I write here. I don't think we have a lot of users who have any clue what the difference between tags and star/flag is, even among power users, and when we can make UI less confusing and simplify it, I think we should take that chance. (Note that this is a general MailNews issue, and I'd very much like to see this in SeaMonkey as well, but I couldn't find a fitting component in MailNews Core, so filing this against Thunderbird.)
It would be great to simplify the UI. IMAP servers are not required to implement user-defined keywords but they are part of the IMAP standard. There are a few special attributes of star, in decreasing order of importance: They're very easy to toggle in the UI. Tags are not. You can navigate to starred messages. You can select all starred messages easily. I would say Stars are easier for users to understand than tags. I know gmail users who love star, but would never tag.
I use stars quite heavily, and I don't think making them the same as stars is a good idea. They have different use cases, and i agree even even novice users understand what star-mark is - though they don't understand tags. I use stars for things i'd like to come back to at some point, having to give it a tag would be too much effort. It could easily be compared to the firefox bookmarking where you just clicking the star creates an "unfiled bookmark". That said, I'm all for making the tagging system easier, and perhaps we could do something like the ff bookmarking system where clicking the star of an already stared mail could bring up a tagging dialog - like firefox with bookmarks. All this would make un-starring harder of course.