Refreshing the category of an Automator service
The following steps solved the problem for me:


Export the workflow from Automator (e.g. to Desktop).
Click on the exported workflow. A dialog appears asking whether you want to open it or install it. Choose Install.
Another dialog appears asking whether you want to overwrite the existing service. Choose Overwrite.


Now the service appears in the proper category.