An s-corp terminated their 401(k) plan. Can they start another 401(k) Plan? Are there any limitations?

Generally, you cannot establish another 401(k) Plan (or any defined contribution plan) until 12 months after you distribute the last asset of the former 401(k) Plan.

Treas. Reg. 1.401(k)-1(d)(3) is pretty muddy on whether the restriction on having the same employees eligible for another 401(k) plan ends 12 months after distribution of all assets from the terminated plan (last sentence of the regulation) or 12 months after the date of termination (third from last sentence of the regulation). Reading the regulation for yourself is probably more illuminating than any discussion I can add here.