Thanks for the additional suggestions. Some of them prompted me to consider other possibilities for the source of the problem, but none panned out.
Yesterday afternoon I called Epson technical support (maybe what I should have done to start with), and spoke with a very knowledgeable and helpful tech. I told her in detail all the things I had tried, and she agreed that I had followed the right steps for the most part. My color management workflow is correct, so the usual suspects (wrong settings in driver or PS print dialog) are not the problem. But like Wayne, she thought it unlikely the problem is with the inks changing over time. She said they have often used inks that are a year or more past the expiration date, with no discernible changes in color.
We came up with a list of things to test changing in the computer/software side of the equation. Change the USB cable, which she said can cause problems. Make changes in the Windows XP print properties dialog. Print through another application other than PS CS4 (I had already done that--printed through LightRoom with same results). Go back to CS3, which I had used to make the initial test prints when the printer was first set up. Try printing where the printer is allowed to manage color, instead of using profiles and letting PS manage color. Finally, try connecting the printer to another computer and printing from there.
I did all those things, with no change in the greenish tint in the prints. (And by the way, some of those test prints were on a version of Bill Atkinson's printer evaluation test image.) So a problem outside of the printer seems pretty well excluded. She had me run another nozzle check using the Auto setting, on glossy paper, since the laser light in the head can detect more subtle problems that way, and will automatically do cleaning cycles until it fixes them. But it found nothing wrong.
It seems the printer has somehow changed, and she still doesn't think it's an ink problem. Her suggestion is to see if new custom profiles solve it--which they probably will, but the question is for how long. That's what I'm going to do. If that doesn't work, or the color changes again over time, the only other option is to send the printer in for repair.
I'll let everyone know what happens, in case someone else runs into a similar problem and starts searching for kindred experiences. And just to be clear on the circumstances here, I'll summarize. The printer was used lightly but regularly for a little over a year and half; and manual (not auto) nozzle checks were performed every week or two. Right after printer setup, several Epson papers were tested with evaluation images--containing gray ramps, color ramps, skin tones, and saturated and unsaturated colors--using the canned Epson profiles. All were excellent, with neutral grays, and matching the calibrated monitor images. Now, new prints on all of those papers, using the same test images and the same canned Epson profiles, show a green tint. The tint is subtle enough that you might not immediately notice it if you weren't comparing to calibrated screen images and truly neutral prints; but is easy to see if you do.