My thought would be to nearly completely rewrite the reqs for the current titles.

Basically keep all the title, but wipe their reqs and start over. Some could be made much harder to scale with the game better, others made easier given the decrease in the number of skills in certain groups, while others could remain the same. I basically feel that 95%+ of the titles were for the < 1000 ranks of the game leaving little to strive for (in the way of titles) for the 1000-1750 range. This would remove the need to deal with the skill combinations in 3.0, and allow for some of the really cool titles to be a lot harder to hit. Granted, it may take a little longer to get all the titles back out.

Falker