Is GDB in good shape? Is BFD library a solution or a problem? I've been a bit dissappointed with GDB at times but maybe I've just been using wrong versions for wrong purposes (debian/unstable for kernel debugging with UML, QEMU etc).
GDB has had some support for tracing, but probably not aimed at step-back support. I think trace based debugging combined with a simulator is an awesome tool. I once upon a time tried out Simics from Virtutech and for certain type of bugs the checkpointing and step-back features are just marvellous. There are also debuggers that can utilize hardware traces (Lauterbach, Green Hills) to do step-back. Adding trace support to QEMU and trace based debugging to GDB would offer really nice kernel debugging environment.
Well - GDB 7 has tracing support that enables step back :-)