Yes, the Duo one's aren't that great. Just a quick one shot, a possible starting point. I'll get to those later though.
Elecman stage:
I don't have much of a problem with the green as a color selection, since it's a nice complement to orange in this case, but for the purposes of an electrical stage it felt off. I chose purple, since blue was taken by the sky. The sky could be reduced back to the darker version if need be. I did change the fans though too, and the ladders. As far as the original goes, I believe a re-examination of the selective highlighting is needed. The green flooring and the ladders needed a touch up there the most. I can go over the concept of selective highlighting if requested.
EDIT: insert into this portion;
Have you compared this to how Elec Man's stage is shown in the trailer by chance?
The trailer didn't, but the screen shots Flame linked to did. They used blue, my original thought as the orange compliment, but since the sky was also, I chose purple.
Megaman:
It was made a little too intense, my apologizes. It was in an effort to keep the popping saturated feel, while retaining Megaman's traditional coloring. Not noticeable as much in NES emulators, for their use of default inaccurate palettes; Megaman has always had a notably teal lighter color, also present in also MM7 and MM8 especially which don't have the same color distortions when rendering their images. This was a mistake to turn it so high though.
Either way... Not sure exactly what I was thinking, now that I review things there wasn't much of a difference otherwise. However in an effort to compensate for GBA contrast differences, ie devs making the game desaturated and bright, here is a contrast adjusted version, with a reverted light color back toward blue more. The main focus here would be the face, has much less bleeding with the white of the eye. Also the outline had been contrasted just enough to take the edge off of the color bleeding between dark armor color and outline.
However, in addition, the palette for the image was a mess, including multiple shades of the same colors, for instance 4 different face colors spread across the sprites. I solidified it into a simple cohesive palette. There was also an unused color shown in the bottom left color table after solidifying, so it was also removed.
http://img713.imageshack.us/img713/8914/yokummmmegamanobjmancol.gifI sound like an idiot after all that. I'm not quite sure what possessed me to put the green that high. The hyper saturation is a very weird style for sure. Certainly sleep deprivation has taken it's toll...
As an additional topic, the shading and coloring differences between NES Megaman and GB Megaman, and how their respective games and original designs have changed and diverged because of the GameBoy palette limitations is something I'll want to get into. The Duo in grey scale is a perfect opportunity to really display why they did what they did, and why the GB colorization project had to go so high color as it did. Really interesting stuff, I've had a few discussions with Zan on the topic before too. I'll tackle it when I have a bit more time though, since its pretty in depth.