Sounds like the battle of the forms is being played out here, Sarah, you should never start the work until you have agreed terms.
I wonder how they would react if you decided to obtain three months payment before starting the work?
Perhaps this is the reason why they had to change contractors?
The solution?
Depends on a number of factors, can your profit stand the fact that you are giving them 90 days credit?
The next question is how trustworthy are these people, you state that they mentioned none of this when you first got the contract, alarm bells should start ringing, did you perform a credit check on this company?
If they expect extended credit from you, what did they give you as an incentive for these special terms? Another site, carpet cleaning?
Never, ever, give something for nothing, you should make it clear, you scratch my back, i'll scratch yours.
Cashflow is king!
30 days is the industry norm, you should stick to this, unless there is a very good reason for not doing so, no point in having the contract unless it is sustainable, all it takes is a couple of late payers, and you could find yourself in trouble.
You could also remind them of your intention to charge interest on any and all late payments, thing is, even if you walk off site, they still owe you, for work already completed, just one more piece of bad news Sarah, they have not accepted your contract either, good luck on this one, and remeber all that glistens is not gold, best of luck.