The subject behavior occurs because AT.EXE does not correctly impersonate the Task Scheduler's account.

The System event log will record:

Event 7901
The At<NUMBER>.job command failed to start due to the following error: General access denied error

The SchedLgU.txt log file will record:

"At<NUMBER>.job" (YourProgram.exe) MM/DD/YY HH:MM:SS ** ERROR **
Unable to start task.
The specific error is:
0x80070005: Access is denied.
Try using the Task page Browse button to locate the application.

The recommended workaround is to use the Scheduled Tasks GUI to schedule the task.