I released an update to Chromatabs today… [Edit: It’s no longer in the AMO Sandbox.]
This version adds the ability to color tabs based on the site’s favicon. (This is off by default; you can enable it in the extension’s preferences.]
Here’s what it looks like with a few select sites:

It’s just averaging the pixels in the favicon, which is why Flickr’s color is purple (a blend of the pinkish-red and blue in the icon). It would probably be better to build up a histogram, and then select the most prominent color… But averaging works fairly well and is easy. 🙂 The code is smart enough to ignore pixels that are almost white or black, which would otherwise pollute the average color. I’ve noticed that a surprising number of sites have black-and-white site icons (eg BBC), so Chromatabs will fall-back to the old method of picking a color for the site in such cases. [Grayscale confuses it sometimes, though.]
I’ve found that using the favicon to determine colors for tabs seems more useful, because the color actually has some relevance to the site. Of course, for sites without an favicon it doesn’t help at all.
Oh, and one more thing (as Steve Jobs is wont to say)…
I’ve been thinking about some ideas to improve the visibility of the foreground tab, which is sometimes hard to pick out (especially with colored tabs, although I think even the default theme is too non-distinct). Here’s a mockup of what I’m currently thinking about — subtle gradients on either side, vaguely as if the neighboring tabs are curving into darkness.

(*cough* I just noticed I styled the wrong tab in the mockup, as the URL bar clearly says “www.blogspot.com” and not “www.flickr.com.” Oh well, no one is prefect! [sic :)])