I read through this whole thread to look for solutions. I, too, have a larg (600M) presentation with videos that stutters and crawls. I tried most of the things in this thread and then found the one that worked. Hopefully my experience will assist others.
1) I tried unchecking the "Back up previous version" checkbox in Keynote Preferences. While some people reported that this worked for them, it made no difference for me.
2) I tried unchecking the "Lock documents 2 weeks after last edit" item in Time Machine Options. This also did not work for me.
3) I tried duplicating the file and then opening it in Keynote. This would seem to work at first, then deteriorate. Why? My thought is that when you duplicate a file you get rid of it's "version history" that Lion and Keynote are using instead of save, but once you start actually going through the presentation it starts a new version history and has problems again. In theory if you don't change anything in the presentation it shoudn't happen, but this only helps if your goal is just presentation. I need Keynote to work so I can edit, too.
4) Finally, I followed fuzzydog's instructions on how to uninstall Keynote 9.1 and reinstall it from my iWork 9 DVD, then upgrade to 9.05. THIS WORKED. I did NOT need to go back to Snow Leopard.
The older version of Keynote doesn't use Versions and once Versions is disabled the problem went away. Thank goodness I actually had the DVD. I'm repeating fuzzydog's instructions below, with a couple of additions in places where I had trouble:
1. Find your iWork 9 DVD.
2. Remove iWork 9.1 using the script supplied by Yvan Koenig. Just deleting iWork is NOT enough - you need to clean up all the iWork files or this won't work. The script is here:
https://public.me.com/koenigyvan
Look in the folder called "For_iWork", then "iWork '09" and then download the file called "uninstall iWork '09.zip". When that has downloaded and opened, click RUN. Wait several minutes while it gets rid of iWork.
The script does not remove your personal templates stored in your user/library/application support/iworks folder.
2. Reinstall iWork from your disk.
3. Next you'll want to update iWork to version 5.05. You can get this here. http://support.apple.com/downloads/#iwork.
There are FOUR update packages: 9.0.1, 9.0.3, 9.0.4 and 9.0.5. Download and install them in order. Yes, I know these are version 9.0.1 and we're upgrading to 5.05 - who knows what's with that.
4. The first time you open any iWork app it will ask you to upgrade to 9.1. Do not do this and check the box indicating not to be reminded again.
If it did not work, check the version number on Keynote (go to Keynote > About Keynote). If it says version 5.1 then you didn't properly uninstall the old iWork. If it says version 5.0.5, then it should be working. If it's not, then this fix didn't work for you (though I don't know of anyone, yet, for whom this is true).
Finally, Apple does NOT read these discussion groups. If you have downgraded your version, then let Apple know by visiting the Keynote feedback page and providing information here:
http://www.apple.com/feedback/keynote.html