I've maintained legacy payroll software (Oracle RPT, predates PL/SQL) and have been marginally involved in migrating clients to the new shiny payroll system. Generally it fails where the client wants the new system to behave exactly like the old system.
The new system usually can handle the required business rules (or it's not too much work to make this happen) but all the processes around those rules are different. eg the new system needs to generate report RW200 to lineprinter 6, daily at 6PM and must be formatted just so (no one reads the first 1000 pages, but the summary page is critical to some obscure business process.)
So, the new system has to print unformatted ASCII to a serial line printer, in an obscure way, on nonstandard paper, that's hard to replicate in a modern report writer. Never mind the already written, laser printed, on-demand reports (or emailed, or exported to excel or whatever) have the same information - it's NOT THE SAME - our users will be confused so it MUST BE CHANGED!.
Rinse and repeat for basically everything else in your system and you've heavily modified your new system to behave just like your old payroll system (and killed any performance improvements, worked out all the bugs etc again). because it's so heavily modified you're basically on a unique version of the new system that only certain programmers really understand. Ant they're going to retire / leave because the project was so shit to work on.
Add the usual government oversight/waste and you've blown a billion dollars. (that's impressive though, I have to say.)