Well, pixel artists are a particular bunch. They don't believe any tool should be used except for the pencil tool. So, to attack such a problem from their point of view, you would need to add each color manually.
Personally, I like to use the best tool for the job, be it the pencil tool, the built-in gradient tool, or the gradient effect.