Permission denied when opening file as root with mode 777

I'm attempting to install and run syslog-ng but I'm blocked with the following error.

Error opening configuration file; filename='/etc/syslog-ng/syslog-ng.conf', error='Permission denied (13)'

I'm running this with sudo and the file and directory now both have 777 permissions. I've used strace and it's definitely an open call that's failing with EACCESS. As far as we can tell it does not change to be another user.

Update: As requested: strace output

[edward.sargisson@apps-mgmt-fe1 syslog-ng]$ sudo strace -f -v -eopen /etc/init.d/syslog-ng start
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib64/libtermcap.so.2", O_RDONLY) = 3
open("/lib64/libdl.so.2", O_RDONLY)     = 3
open("/lib64/libc.so.6", O_RDONLY)      = 3
open("/dev/tty", O_RDWR|O_NONBLOCK)     = 3
open("/usr/lib/locale/locale-archive", O_RDONLY) = 3
open("/proc/meminfo", O_RDONLY)         = 3
open("/usr/lib64/gconv/gconv-modules.cache", O_RDONLY) = 3
open("/etc/init.d/syslog-ng", O_RDONLY) = 3
open("/etc/init.d/functions", O_RDONLY) = 3
Process 4802 attached (waiting for parent)
Process 4802 resumed (parent 4801 ready)
Process 4803 attached (waiting for parent)
Process 4803 resumed (parent 4802 ready)
Process 4802 suspended
[pid  4803] open("/etc/ld.so.cache", O_RDONLY) = 3
[pid  4803] open("/lib64/libc.so.6", O_RDONLY) = 3
Process 4802 resumed
Process 4803 detached
[pid  4802] --- SIGCHLD (Child exited) @ 0 (0) ---
Process 4802 detached
--- SIGCHLD (Child exited) @ 0 (0) ---
open("/etc/profile.d/lang.sh", O_RDONLY) = 3
open("/etc/sysconfig/i18n", O_RDONLY)   = 3
open("/etc/sysconfig/init", O_RDONLY)   = 3
open("/usr/share/locale/locale.alias", O_RDONLY) = 3
open("/usr/share/locale/en_US.UTF-8/LC_MESSAGES/initscripts.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/en_US.utf8/LC_MESSAGES/initscripts.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/en_US/LC_MESSAGES/initscripts.mo", O_RDONLY) = -1 ENOENT (No    such file or directory)
open("/usr/share/locale/en.UTF-8/LC_MESSAGES/initscripts.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/en.utf8/LC_MESSAGES/initscripts.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/en/LC_MESSAGES/initscripts.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/etc/sysconfig/syslog-ng", O_RDONLY) = 3
Process 4804 attached (waiting for parent)
Process 4804 resumed (parent 4801 ready)
Process 4801 suspended
[pid  4804] open("/etc/ld.so.cache", O_RDONLY) = 3
[pid  4804] open("/lib64/libnsl.so.1", O_RDONLY) = 3
[pid  4804] open("/lib64/librt.so.1", O_RDONLY) = 3
[pid  4804] open("/lib64/libnet.so.1", O_RDONLY) = 3
[pid  4804] open("/lib64/libdl.so.2", O_RDONLY) = 3
[pid  4804] open("/lib64/libc.so.6", O_RDONLY) = 3
[pid  4804] open("/lib64/libpthread.so.0", O_RDONLY) = 3
[pid  4804] open("/etc/eventlog.conf", O_RDONLY) = -1 ENOENT (No such file or directory)
[pid  4804] open("/etc/localtime", O_RDONLY) = 3
[pid  4804] open("/etc/syslog-ng/syslog-ng.conf", O_RDONLY) = -1 EACCES (Permission denied)
Error opening configuration file; filename='/etc/syslog-ng/syslog-ng.conf', error='Permission denied (13)'
Process 4801 resumed
Process 4804 detached
--- SIGCHLD (Child exited) @ 0 (0) ---

As a test, we moved the syslog-ng.conf somewhere and copied it back - which made it work but doesn't help. If I use chef to replace the file then syslog-ng will not start.