Problems with Time Machine endlessly preparing

We use Time Machine with a network disk connected via AirPort Extreme for backup in our household (writeup), and it’s generally a great solution. However recently my wife’s laptop had got stuck in an endless “preparing backup” situation. There didn’t seem to be any significant details in the error log, and when I ran a …