In OSX 10.8.2, I created a service using Automator and saved it in ~/Library/Services. The service receives selected messages in Mail.app. It shows up in the list of services when I click on the "Mail" menu. When I click on the service, it executes correctly. It also shows up in the list of services when I try to assign a keyboard shortcut to it in System Preferences. My keyboard shortcut doesn't appear to conflict with any other. To make sure of this I've tried assigning very improbable shortcuts involving 4 or 5 keys.
Somehow the shortcut never "registers", i.e., it doesn't appear next to the service name in the "Services" submenu of "Mail" and using the shortcut doesn't produce any result. What could be causing this?
