Interesting resolution to this. I took the car back to the mechanic. He put the computer on it and checked the coolant temperature data, which looked fine. So probably not the coolant sensor.
Then he started doing a little research on the car's computer. Somewhere in his reference he found that when you change a part like the idle relief valve, you need to disconnect the battery to zero the computer's memory, since it will have decided (after several weeks of idling too fast) that the fast idle speed is the correct one.
We disconnected the battery, let it stand 5 minutes, reconnected it, and it idled completely normally. I'm doubly happy about this because I was beginning to wonder if I'd shelled out $300+ for nothing.
Jon