I'd like to point out two problems.

The first, and most important to me as a physicist, is that he ignores all the incredibly powerful predictions you can make if you treat time like a sort of space. (The difference between time and space is that in the equation for distance between two space-time points, as you go farther in space, it's harder for a particle to visit both points, but as you go farther in time, it's easier to visit both points - time gets a negative sign that space doesn't).

For example, energy conservation can be derived from Noether's famous theorem in just the same way as momentum conservation - but momentum conservation comes from the properties of space, while energy conservation comes from the properties of time.

The second is, as Yvain would say, that his argument about being able to split things up into "frames of a movie" and fit them back together proves more than he bargained for. Because the different parts of space follow laws as well, with electrical fields and non-pointlike quantum-mechanical atoms extending through it. So you can split space up into points, and by Barbour's argument the points just go together based on the laws that govern how electrical fields or atoms work.

So there's "no space" and "no time," except that you have a big pile of points that can suspiciously only be put together one way in accordance with physical law. The completeness of this destruction then circles around to become boring if you simply define spacetime as "the collection of points that physical law works on."

What is meant by "exist"?

The interesting bits (i.e., not classical physics or philosophy) start around 38:00 with the Wheeler-DeWitt equation.

And for a totally different view: http://www.thersa.org/events/audio-and-past-events/2013/time-reborn-a-new-theory-of-time-a-new-view-of-the-world (ETA: in interests of full disclosure, I follow the consensus and don't agree with Lee Smolin.)

If we view time as the increasing entropy of the universe, it is sort of hard to deny. Maybe, it is "emergent" only above the quantum level, but so what?