I know this is an old thread, but I never found the answer online, so I thought I'd update this with my solution.
First, granting "u+s" or SETUID permission isn't a good idea because it will then run "at" as the owning user (probably "root") whenever a user executes it. I'm not sure how much permission that gives the user, but I'm thinking that "root" can get "at" to run just about anything.
Now, the solution I found is to find your "at.deny" and/or "at.allow" files (in my case, SUSE 10, it is in "/etc/"), and make sure these files have "read" permission for all users. I don't know why this isn't the default, but it wasn't for me. Once I did this then the error message "You do not have permission to use at" disappeared! I guess it wasn't able to check who didn't have permission in "at.deny" when I ran it as my owner user, so it just denied everyone!
I've got some issues with /var/spool/atjobs now, so I'll update when I've figured that out.
Last edited by teqteq; 10-22-2012 at 10:42 PM.
Reason: Part of solution needed more work