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?

Simple answer: No, time doesn’t exist. Barbour is correct. On the platonic (universal) level (the fundamental level of reality), all is timeless. The appearance of time is a consequence of partitioning reality into cellular automata: when things take on the appearance of cellular automata they will seem to behave like systems; that it is say, they will seem to have inputs, produce outputs, and processing. Sentience too is closely tied to time, and indeed (as I realized long ago and stated on both wta-talk and ‘Overcoming Bias’), consciousness itself can be considered a special case of the illusion of time; it arises from a coarse-graining of our self-models due our limited introspective capacities. Just as a fundamental ignorance or ‘smearing’ of physical microscopic properties gives rise to thermodynamic properties, so too, lack of complete knowledge about all our internal goals produces the illusion of qualia.
So what am I saying in short? Reality at the deepest level is continuous; on that level it’s timeless; but mentally partitioning reality to create a discrete model (cellular automa) results in the illusion of time. Ergo, qualia is a special case of this illusion, whereby goal-directed computational systems (cellular automata with goal systems) are further coarse-grained, and there is corresponding uncertainties in the internal goals of these systems (the smearing or blurring of internal goals manifests as ontologies/categorizations/qualia).