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).