I used to work for Motorola specifically testing cellular networks for Verizon Wireless and Sprint PCS. I think Verizon uses Lucent in NYC, so I can’t speak with 100% confidence on them.
However, most base stations (the actuall equipment at the bottom of most cell towers) have a battery back up or, in some cases, an emergency generator. Motorola recently had base stations still operational after the major earthquake in Japan and while standing in 2 and 1/2 feet of water after the flooding down in Mexico. These are set to handle local disruptions.
However, these base stations are connected to some kind of centralized controller. The centralized controllers are the real brains behind the whole network. They usually control dozens of base stations and are rather distant from the base stations they control, most likely in a nice comfy building, but without the back up power. (these things suck juice like crazy and are very warm to work near)
Most companies plan for power outages. Most adjacent base stations are connected to different controllers. That way if the power to one centralized controller is lost and all of its sites go down, the adjacent sites are still operational and there is still quite a bit of coverage.
However, when the entire electrical grid goes down, all of the centralized controllers go down. The individual base stations might be up because of their batteries and/or generators, and you might even see a signal on your phone, but most likely, you won’t actually get connected.
Sorry if that was too much detail.