My feeling is that if you're going to change something, the "complete" icon is probably the one to go for - that ought to be more managable for most people.
It would be VERY useful if the list of message icons you get when you post a message said what they represent, rather than the two rows of icons without an explanation we currently get.
Having said that, I think that putting "complete" into the header is probably enough, without playing "spot the icon".
