I ran the Auto Nozzle Check and Cleaning utility, which led to a manual nozzle cleaning. And that did the trick. I guess I expected those utilities to deal with gaps or streaks in prints... not uniform color changes. But now I know. Probably the problem arose because it'd been over a month since I really printed anything, and apparently you need to print a few pages a month to maintain quality.
(The replacement ink cartridge was manufactured in December 09, so I doubt its age was a factor.)