Very disappointing, but seems to be the way with cloud software these days. They can just take features away at the drop of a hat!

In the short term, I suspect you will have to do as they advise and use the HMRC Basic PAYE Tools software, even if just as a stop gap. At least it's free and does the job. I do this for another client, who has always refused to pay the extra for QB Payroll... a wise man with hindsight!

Best of luck.