Split timeline is my guess. A common theory of changing history is that it splits off into two realities. One where things happened as they had originally, the other where a new reality starts off where the change occurs and goes in a different direction. Not sure how they're going to reconcile it all though.
But what was he doing on the plane in the first palce? In 2001, he was in a boat race around the world. Did he finish? Did he get together with Penny?
But, and there's a big but, how did Hugo's Dharma van come through?
If the island was submerged, then he couldn't have gotten stranded there, so he presumably finished the race. Why he would coincidentally end up on the same flight from Australia, is a bit of a stretch, though.
I know..."fate". Also known as "writing copout".
Why was Claire not traveling with Boone, and yet she was there at the airport when they landed?
Did you notice how after Jack saves Charlie on the plane, Desmond is no longer there? Maybe by saving airplane-Charlie, that means that island-Charlie never died to warn Desmond about the boat, and by some course of events Desmond ended up dying instead.