Keynote '09 can't play slideshow again unless restarted
The only solution I found so far (by experimentation and searching the web) is to set the display mode to mirroring instead of presenting on a separate display. It will then let me play and replay the presentation without the error message or requiring a restart of keynote.

(Mac OS X 10.6.8 and Keynote 5.0).