Now... ahh ha.
More than likely they are being anal retentive about Root.
Root is a crappy thing to have to use to do automated things. It happens, but many won't/don't know how to make it available.
Probably comes down to a setup using some kind of PAM thing or perhaps "root" has a compiled in option for ssh/sshd to not allow things. There are weird options usable to restrict Root in custom compiled sources, all without config options evident.
You should see entries in the /var/log/auth.log for me...
Mar 1 00:32:57 omg sshd[30118]: Accepted publickey for root from XX.XX.XX.XX port 34837 ssh2
Mar 1 00:32:57 omg sshd[30118]: pam_unix(sshd:session): session opened for user root by (uid=0)
I'd be looking as the PAM session setup, I'm betting its there.
