The real issue with critical failure is not in the concept but rather the implementation. Using a D100 having an always happening critical fail roll is much better implemented. With the D20 it just seems to happen to often.
A further tweak that could make since is to limit critical failures to two circumstances.
Character does not have the skill in question. So when a character for example tries a lock pick but does not have Sleight Of Hand, then even with modifiers a natural 1 is a Critical Fail.
Conversely if the character has the skill but is somehow hexed, cursed, injured or whatever where even with modifiers the adjust score is a 1 or less there is a critical fail.
I personally like the risk of a critical fail as it adds suspense to the game. Using lock picking as an example BTW, there are other options. I always have a Wizard keep a Knock spell on stand by. I also always have my strength character carry an extra weapon just for door/chest bashing.
As for critical failures in other skill checks in the game they make sense. Trying to hide in shadows, even the best thief would occasionally with a lapse of concentration or some unexpected event (kicking a small pebble he did not see) can fail the hide and even potentially draw attention to himself. What about conversations with Charisma, the same thing. Maybe you made a cultural fopaux while speaking to the person. This happens to even the best public speakers and negotiators. This could result in a failure, even a critical failure under the worst cases.
Couple of other tweak ideas for the game that might help.
Turn off critical failure on Easy Mode or even scale it. Easy Mode for example has no auto failure period, the next mode up has auto failure but no critical failure, the harder modes have critical failure.
Another idea is a variant I see often used in Table Top games, a natural one means a reroll, a one or a two on the reroll is a Critical Failure.
