I believe that I have solved this.
The problem did not go away by itself. After rebooting Automator apps either worked, or they did not work.
This was true for all automator-made apps, not just the one described above. Nothing do to with Desktop
or creating a folder there. Sometimes there was no problem after three successive reboots, then it came
back again. All automator-made apps were blocked on my account, but not on a second user account.
The origin of the problem is, apparently, that I used two Automator-made apps as a startup item on login.
This has always worked fine under Snow Leopard, but it seems that lion cannot handle that. I suspect some
kind of timing problem. The apps do seem to start a lot faster in lion, and perhaps they somehow get
into each others way and then block anything else.
Now I have combined the two apps into a single one, and the problem has not come back.
In that sense I consider it solved, but I would still like to know what is really going on.