I don't mean to offend, but neither logo is adequate.
In my view we are competing directly with Windows, Mac, and Ubuntu. All have a superior logo. All have a simpler, cleaner design.
I don't think Mint needs to rebrand. It just needs to simplify, clarify, and evolve. Look at the competition, streamline, and then dominate them.
Mint is already a better OS. It's faster, easier, more solid, more feature filled out of the box. It just works.
Step One I think is losing the "Linux". Windows isn't DOS Windows. Mac OS isn't BSD Mac. You know why? Nobody gives a #&%$. Just make it Mint. Then riff off the original logo, which is not bad actually, lose the L, give it a little more contrast, simplify it. Make a new slogan. I don't know how to do vector art, or I'd do one right now. Maybe I'll sketch one up and gimp it.
