The message about how other applications must be restarted is expected. Only applications launched after a keyboard shortcut has been installed know about it.
Are you also saying that you can't get a shortcut to show up in the recorder field after you type it? You might read this thread:
http://forums.omnigroup.com/showthre...0725#post70725