I'm not aware of any grace period for delaying enrollment or not allowing deferrals.
I think you have a reasonable administrative delay (changing providers) for delaying/suspending the deposits, until the accounts can be setup.
One administrative issue might be those payrolls are going to the old provider, in which case I'd assume you would have to enroll/default those participants into the old program.