Since CS3 Illustrator has received powerful color manipulation tools that are relatively little known. Select the menu Edit/ Edit Colors/ Recolor Artwork to discover a plethora of features.
In the Edit tab you can change the brightness, hue and many other aspects of several selected objects at once. It also allows you to create color harmonies with a color wheel besides other cool features.
In the Assign tab you can recolor your entire job with a new set of colors using the color groups functions.