[freebs]

Webmaster tools will tell you about duplicate titles even if there are only a few. A few duplicate titles won't penalize your rankings. Perhaps this is your case. I've definitely seen results for sites that have had 60% of their page titles as dupes.

You also have to realize that it's very important on what you are changing the them to. You should have done keyword research to see how often people are searching for particular terms. If you changed the title to be a non-duplicate but used some obscure words that a normal person would never use, you won't see many results.

Titles are just one piece of the pie, they should be consistent with everything else on the entire page, including the meta description, headings, content, image alts, links, etc.