I'd actually go for some fine-grained advanced recolor options. Not so much element based, but perhaps some options that could limit the HSL shift to any parts of the skin which are within a given HSL range already. For example. right now if I want to recolor a skin to red, but the menus, toolbars, etc., are slightly tinted rather than being straight gray, I have to have all that stuff a funky pale pinkish-gray in order to get the titlebar/start menu red. What I'd like to be able to do is recolor only the strongly saturated parts to red, and completely desaturate the low saturated parts.
Probably wishful thinking though. Just gotta fire up PSP and do it manually most likely.