I actually rather like the difficulty increase, it should have been implemented much better.
It seems like it should work rather like a wizards spells per day. Some advantages and disadvantages there (you will always have at least a 5% chance to cast but never more than a 95% chance) at which point you have to way infinite spells per day (given enough tries) vs a percentage chance of failing while in combat.
I prefer a mixture of abilities so that you're never completely useless. That said, if I were doing a Truenamer fix, here's what I'd do.
1) Each time you use an utterance, the base DC of that utterance rises by a certain amount. The difficulty increase caps at a certain point; past there, it gets no harder.
2) Every X points your check is over the base DC increases the result in some fashion. More damage, higher save DC, what have you. There's a cap on this too. A result of 900 does the same as a result of 800.
3) DCs reset after resting.
4) Truenaming gets smacked around a little with some special rules so you can't pull the usual skill shenanigans. I'd need to toy with this one, do some math, but it should eliminate splatdiving for bonuses.
Each time you use your utterances that you can augment most of the time, they become less potent on average. Each time you use the more powerful stuff, it gets harder to use. You should always have a reasonable chance to use an utterance, thanks to the caps, but there's resource management to consider.
...actually, let's add a new rule. Utterances where you get the weakest possible result don't add to the base DC, and you can voluntarily use a lower result. That gives you more control over when to pull out the stops.