I agree that this is an issue, but I think the answer is simply using a very flexible basic data representation (which admits invalid state) and then using predicates to refine it. e.g. starting with a list of (start,end) intervals and then adding predicates for valid intervals (start <= end), ordered, non-overlapping and continuous.
If any of the requirements change, it's easy to either add more predicates or relax/even outright remove them.
If you play your cards right, you can even get your type system to alert you to every place in your code that needs to change when you change the constraints.
I don't deny there's a certain art to that, and I can't explain it all myself. But I don't even necessarily mean amazing clever type tricks like you might see in Haskell or something, I mean that something as simple as "I've changed the definition of what a 'Customer' is in some fundamental manner, so I'm going to rename that class to 'CustomerNew', use the compiler to point me at every single place that breaks, audit it, change the local name to CustomerNew, and then, once everything is fixed, use my IDE's rename feature to rename CustomerNew back to Customer before my final commit". Many times you can get by just by renaming a field or something to similar effect, but in the worst case you may need to audit everything.
It's one of the more tedious bits of the job sometimes, but net-net this can still be a timesaver, if you account for the full cost of the trickle of bugs this sort of thing can prevent.
If any of the requirements change, it's easy to either add more predicates or relax/even outright remove them.