I guess the first question would be: why not just add color and shading right in Illustrator? Especially for a logo design, where you’re going to want maximum flexibility in scaling, and consistency in colors. Gradients, gradient meshes, blends– you can do a lot of shading right there, all vector-based.
If you really want to do it in Photoshop, don’t use the Paint Bucket. Clunky tool. Make a new color layer below your black outline layer and fill selections with your colors of choice. That way there’s no gaps between color and outline and you can do any amount of shading to the colors without worrying about bleeding into your outlines.
—
It is easier to destroy than to create.
More fun, too.