So you have changed the color cartridges?
What about the black ink cartridges? How do you know they're ok?
In my experience, bad color quality was the result of low blank ink, so you might want to look into that.
Also, can you make sure you're not printing Drafts. (Usually in Print setup)