I know you already worked out your problem, xroox, but I just ran into a very similar problem and found a much simpler solution. I thought I'd record it here for anyone else who might run into this in the future.
In my case, I was tying to use Automator to record a service that would simply click the Fast User Switching menu in response to a keyboard shortcut. Like you, my workflow ran perfectly as long as Automator was open, but failed with the "'Watch Me Do' encountered an error" message if it was not.
Turns out, in Mavericks, even Finder needs special permission to control your computer this way.
To give it the permission it needs, go to System Preferences > Privacy > Accessibility and select the checkbox next to Finder (you'll probably need to click the padlock in the lower left corner first and enter an admin password).
I suspect the same instructions, but for Firefox instead of Finder, would have worked for you, xroox.
UPDATE: On further review, the "Watch Me Do..." error will be generated every time the service is invoked if the currently selected application has not been granted permission to control the computer in the Privacy > Accessibility prefs. For my purposes, I guess this means that I need to grant permissions to my most frequently used apps on a case-by-case basis as needed, or remember to manually switch to Finder first.
Anyone with a better solution?
Message was edited by: phoward8020