A bit late coming back to this party, but I may've just had an AHA moment.
Keynote is barking at the Office Theme, which is the standard theme that your presentation's built on, most likely.
Themes can include font information among other things ... the font theme controls which fonts are used by default for headings and other text. You may have used entirely different fonts for all of your text, but Keynote may be assuming that Theme Font = Used Font. And complaining about it.
Try creating a new font theme that uses heading and body fonts that are installed on all of your target platforms (whatever you're using now, for example, since those seem to be working out well). Apply the new font theme then try opening in Keynote.