Decius - 10:00 am on May 6, 2008 (gmt 0)

This happened to me three times.

I tested the different titles and found that the addition of a specific keyword flipped everything out of the SERPs.

Altering or maintaining the titles and removing those keywords fixed it every time.

My guess is that if the inbound links match the titles too much, Google doesn't like it. There is no hard and fast rule - but I would definitely, definitely revert back to the old ones. Each time it took about a week to re-propagate, which I know is a stressful pain.