atd stopped working on OS X 10.10.3

That message suggests that you don't have the correct privileges to run atq. Try running it with sudo from the command line to see if that helps i.e.:

> atq
atq: cannot regain privs: Operation not permitted
> sudo atq
Password:
>

I just installed the 10.10.4 update from Apple today.

I noticed that the at command works. But that is not all you have to do to enable the service. What you have to do is to edit the /System/Library/LaunchDaemons/com.apple.atrun.plist and change the "true" to "false" after the disabled XML section. Then you can use command

 launchctl load /System/Library/LaunchDaemons/com.apple.atrun.plist

to start it up.