Researchers have been following the penguin population off the tip of the West Antarctic Peninsula since the 1970's. Winter air temperatures in the region have climbed a significant 5 to 6 degrees Celsius in recent decades with a concomitant loss of sea ice; this region is one of the fastest warming areas on Earth. Assuming that the loss of sea ice would be a key factor in the reduction of penguin populations, researchers assumed that Icebound Adélies (Pygoscelis adeliae) would be hurt by the loss of sea ice; in contrast, it was thought that the more free-roaming chinstraps (Pygoscelis antarctica) would hunt better with less ice. Instead, from the 1980's forward populations of both species plummeted by more than half across the study sites.
In seeking to ascertain the cause for the penguin decline the researchers found that the krill population (see http://en.wikipedia.org/wiki/Krill) had dropped by 80%. Some of that reduction has to do with the resurgence of whales and seals following the end of their hunting by humans. But, causation may also come back to loss of sea ice. Young krill grow while hiding under ice masses. Thus, less ice means less krill, and that means both the Adélies and chinstraps go hungry. The loss of krill is especially bad even for chinstraps since (unlike Adélies) these birds do not live elsewhere in the Antarctic.
Other researchers have commented that the problem may be more complex yet. They note that the influence of climate change may be reducing photosynthesizing phytoplankton (see http://en.wikipedia.org/wiki/Phytoplankton), an important food source for krill. Other researchers have noted that some albeit small, but perhaps growing chinstrap populations have been found nearby in areas they have not traditionally inhabited.
If the krill population is declining, for whatever reason, the base of the food chain may be collapsing, with all that such implies.
The research on the chinstraps and Adélies penguins can be found at http://www.pnas.org/content/early/2011/04/06/1016560108.full.pdf+html.