I don't think the Omniscient log-the-world Debugging is practical, but if we just had some form of deterministic replay, we could take snapshots or even cheaper memoizations at certain points in the program. Going backwards is simply a matter of going back to the last checkpoint and going forwards to the point where you want to stop.
I agree that the key is UX, and as Gilad said in the blog comments, they aren't necessarily technological (once we know what the right experience is, we'll build the technology!).
Disclaimer: I work for MSFT, though I study this problem in research (MSR/MSRA).
I have definitely noticed a correlation between developer debugging skills and clean code practices. Obviously, this doesn't mean one is causing the other, but I would love if there was any research looking into this.
It does make me wonder if our time would be better spent finding ways to improve consistency and professionalism in our practices, rather than another new tool to get you out of the mud.
I believe more in the latter school, though of course, they are both extremes and I'm a moderate. The mud is unavoidable and we might as well build winches to pull ourselves out rather than spend time trying to carefully avoid it.
But even this definition feels too confined. There have been some developers I worked with that must have started out this way and then learned 'engineering' practices. They were all exceptional to work with. I wish more of this group could get to that level. Hence my interest in putting bread crumbs on the path to learning, rather than yet another pill to lose weight fast.
Debugging is as close to experimental science as we get in computer science. It is the act of understanding a complex system, and even if we built that system entirely by ourselves (unlikely), it eventually "gets away from us" and takes on a life of its own. It is impossible to understand everything, and debugging is a great way of allowing us to forget details and uncover them later.
So far most of the tools have been created in a very strict, single purpose way. While that's a good engineering approach it also leads to limitations that are hard to overcome. I do remember the early days of Eclipse when they had to build their own java compiler to be able to pull out enough data for the IDE. And that's the simplest example. Or think of the days before JMX.
Obviously this is not a simple problem to solve. I think the only way we could fundamentally change things is to completely rethink the way programming models/environment are thought.