Keyboard shortcut for Service in OS X doesn't work

Did you change the input type from selected text to no input?

If it's not that, there is also a bug on 10.7 and 10.8 where the shortcuts for Automator services don't always work until you hover over the services menu from the menu bar. It doesn't affect just new services, so it often makes Automator services unusable.