I would consider the speed of the "ultimate error handler" (i.e. whatever prints the traceback and kills the program) in the interpreter to be moot, so long as it takes a small fraction of a second. Optimizing Python's speed it crashes super-fast due to an *unhandled* NameError in your program seems folly.
Regarding more informative messages for (e.g.) IndexError, would those just apply to built-in types as they're the most universal, or should some additional introspection be done for similar ducks?
If it's useful/there's interest, I could try to do some analysis of Python questions on SO and see what the most common errors are. I'd guess things like "'NoneType' object has no attribute ..." would probably be up there, but that's a whole can of worms as to why someone's trying to call a method on, index, etc. something they accidentally whacked (a = a.sort()).