I created a simple DTS package, I executed and it worked just fine.
Then I scheduled it and tried to execute the job. The job failed. It consisted only of one step which executed the package, so I was pretty speechless.
I opened job's history. It looked pretty awful (many lines of text without newline characters), but I managed to find a few occurrences of 'Access denied' phrase.
Then I remembered that there was something like 'Script file directory' textbox in 'Copy SQL Server Objects Task' window. I also realized that the domain account that I use to run SQL Server Agent service has very limited permissions.
I changed the path in 'Script file directory' textbox to one that SQL Server Agent could access and this time the job executed.