<rant>
Every few months I play this annoying little dance with my motor insurance company. They want to be paid on the 1st of the month, problem is that I get paid on the last business day of the month. If my cheque hasn't cleared (when days are next to each other) often I am late.
So I pay a day late, and a week later I get an letter telling me my policy will be cancelled if I don't pay by 12:01am on the 1st of the next month. If that month has been expensive (xmas, holidays, etc) and I don't have $120 we run into this little dance. I'm late, they cancel my policy, and then reinstate it when I pay a day or so later. This happened for the last two months, and until I pay on time once, I don't get my usual payment date of the first business day of the month.
Of course, the insurance company can't change the billing date to something nice like the 5th because my policy runs from the 1st of the month. I'm guessing that I'm late about 50% of the time because of this. If I had a credit card with a decent limit, rather than the $200 and $250 I have on my two, then I wouldn't have this problem.
Moral of the story? Being inflexible is bad business. The credit rating situation in the US sucks and until I get a credit card with a limit higher than 2 days salary, things like this will continue to piss me off.
</rant>
Another idea - can you set up automatic debits and get overdraft protection from your bank, assuming overdraft applies to automated payments.
Lastly, try and get the phone number of the people at the insurance company who can really help. I've been having problems with my mortgage company and finally got the number for the Quality Assurance people in the Executive Offices. They really get things done. Your ins company may have some similar folks.
Good Luck.