You may have noticed that Keynote took a while to save your presentation file after you added the movie file. This is because Keynote (by default) copies all of the media used in your presentation into the Keynote file. This is a good idea because it simplifies the process of transporting your presentation to another Mac. It means that when you take your Keynote presentation on the road, you have to take only one file with you. Let's check that all of the elements made it into your presentation file for backup.
Fonts used in a presentation must also be installed on the presentation machine. If you use fonts that are not installed with iWork '06 or that are not OS X system fonts, be sure to install the needed fonts on the new system. Fonts, however, are not saved in the Keynote package. Any fonts used in a Keynote project on one machine need to be installed on any new system where the project will also be used.
If you ever need to access an element from a presentation and don't have access to the original files, you can borrow it from Keynote. Control-click (or right-click if you have a multi-button mouse) the Keynote document and choose Show Package Contents. The folder contains all of the elements of your presentation. You can Option-drag any of the elements to a new folder to copy them.