Restumping, part two

So, apparently, most houses stumps are around 450mm deep.  Our quote was for stumps 650mm deep.  Now, after two days of digging, the guys doing our stumps have found all the ones around the outside of out house (the inside ones, ie most of them are fine) are best part of 1m deep.  This means the job is going to cost more.... I just get a bit of a sinking feeling.....