tedster - 7:07 pm on Sep 5, 2008 (gmt 0)

Originally the title was "[region] [industry sector] news" and "[region] national news". I changed this to have the headline inserted before so that the titles would never be duplicated.

A change of title tags on that scale can cause Google to reevaluate all those urls. I'd suggest you just wait it out for another week or so. It sounds like you did make a good change, but one that is not quickly assimilated.