This was a kind of non-regeneration regeneration. The eighth Doctor, Paul McGann had last been seen nine years before in "Dr Who: The Movie." So what we're to believe is that sometime in the blank space between McGann and the present the Doctor had regenerated. Thanks to the BBC, we weren't around to see it.
This idea is given some support by the fact that the giant Time War between the Time Lords and the Daleks took place sometime after Sylvester McCoy's shift and before Christopher Eccleston shows up on our screen. So Paul McGann could well have fought in the war, been killed, and regenerated. Which, BTW, brings up an interesting point about Time Lord soldiers, you probably have to kill them 12 times before thay stay down!