Could shingles that are not flat be caused by stapling the sheathing rather than nailing?
If your contractor is claiming the fasteners are loosening from the sheathing it is a simple matter to verify. On the roof any nail or staple that has pulled away from the rafters will have pushed up or through the asphalt shingles. If it has only pushed the shingle up carefully pry the shingle up further and peer under it. You should be able to see the nail head or staple crown.
If several fasteners have loosened along the same edge or seam an obvious bounce will be detected when pressure is applied over it. Fasteners pulling from sheathing (whether staple or nail) happens to the best constructed roof even if the fastener schedule is followed. Over time expansion and contraction slowly work the fastener loose.
Longer, additional, and accurately set fasteners may be needed (or lacking) for the sheathing.
Unless the felt paper under the shingles was crumpled in a knot or completely 'FUBAR-ed' it may be that rolled roofing was used as an under-layment (not common under shingles, but possible). Rolled roofing is known to wrinkle if installed in long lengths (more than 15-20 feet?).