I've heard that TPTB said that the pilot episode contains clues to the show. I recently watched the pilot, and I realized something. In the first scene, when Jack wakes up, he looks up and sees unharmed trees. I guess this means, Jack didn't fall down from the sky, he was just teleported from the plane. This makes sense, if you remember Ben being teleported to Tunisia. The same happened after the Ajira flight too. He woke up near the pond.
And everybody thinks that 48 survivors from a plane crash without any real damage would be a real miracle. Sayid says that "Nobody is that lucky." in the pilot episode. That means they were all teleported to the island I think.
This reminds me of the teleportation system of Enterprise in Star Trek.
And the tennis shoe in the first scene, just means that Christian Sheppard's body is somewhere on the island. He wore tennis shoes apparently.
John Locke being able to walk isn't about time travel I think. Because producers debunked the time travel idea once. I guess they meant to say, "No time travel, yet." The thing is island itself has healing abilities. This, again, reminds me of the Doctor with a healing thingy in Star Trek.
I guess, something from outer space is at hand.
The island itself is a "lost" spaceship I think.