Richard's soylent green explanation covers everything really well -- I hadn't even noticed that little throwaway frame with the projected population decline, and I'm perfectly happy with this theory in its entirety. That puts the population decline at ~842 every year -- just another century would have dropped the population to nearly 2,000 passengers! (I'm sure the math is much more complicated than I'm making it out to be, but even simplified that's quite impressive.)
I did want to contribute a few additional thoughts, though.
I've been thinking for a while that it was strange for the AXIOM to be called a flagship of a fleet of starliners, yet throughout the course of the movie, the credits, and the additional DVD and Blu-Ray commentary we hardly see these ships, and only ever from footage taken on Earth before and during the mass exodus.
I've read around online that the other ships went to other locations in the Kuiper Belt and to other extra-solar sights; however, not all of these vessels were Executive Starliners, and considering the height of luxury advertised on BNL commercials I'm betting the other ships weren't as nice, and wouldn't have lasted as long in space without guidance from BNL's CEO.
So maybe the AXIOM 1) cannibalized the passengers and resources from other ships in the fleet over the course of 700 years, and/or 2) routinely traces the last known locations of offline ships to salvage bodies and resources to sustain its own crew and passengers? Traveling long distances isn't a problem, obviously, if it goes from the Kuiper Belt to Earth in fifteen seconds or so -- especially not if it's siphoning fuel from dead ships.