Wordservice: "The 'Lowercase' service could not be used

I’m running a fully up-to-date Leopard system. Often, when I try to use functions under the “Convert” submenu of services, I receive a message that “The ‘Lowercase’ service could not be used”. I get it not only for lowercase, but for all of the capitalization changing commands. Oddly, ROT 13 does work.

I experience this in Keynote, but not in other applications, such as TextWrangler or Mail (I’ve pasted the text that isn’t working in Keynote over to them, and it works fine.)

Sometimes, oddly, it does work in Keynote. Sometimes doing ROT 13 twice get the other services working–but that may be coincidental.

Any leads? I just love this functionality.

This has to be either a Keynote or Leopard issue because all commands of WordService work more or less the same (e.g. Lowercase, Uppercase, Rotate etc.) and do not depend on the current application.