"It turned out though that payroll for such a broad range of employees was much more complicated than had been envisioned back when the project was started nearly a decade ago."
Really? turned out?
Its been known for a looong time that large scale Payroll is difficult since there are so many micro rules and variations to apply and can change yearly with legislation.
See the famous Chrysler C3 1993-1999 for a classic example.
then you add PeopleSoft hahahahaha
and then IBM hahahahaha
Incompetence never goes out of fashion.