Fry was frozen in Old New York's Cryogenics Lab and went 1000 years into the future. When he woke he was in New New York. Old New York is under New New York but the Cryogenics lab stays in the same spot?
Consider that the purpose of the Cryogenics Lab is that people be thawed when the right time has arrived. It does not seem unreasonable that people would continue to want to be frozen through that millennium, nor that some would be thawed in less than one thousand years' time. It is therefore quite possible that, as New New York was built over Old New York, the lab relocated to remain on the surface, where its customers were. This does rely on the equipment being movable, but the worst case I can think of is that one would need to hook up a generator (which a cryogenics lab should have anyway in case of grid-power outages), then move the entire building, with the equipment inside. Considering how much people are willing to pay for cryogenic freezing (it's an awful lot!), that shouldn't be too problematic, and would probably be good business sense.
The building looked tall... it's possible that the ground of New New York was just at a different floor level than that of Old New York. Maybe, for example, they changed the base of the building to be the 10th floor, and then sealed off the lower 9 that were now below ground level (and part of Old New York).