I have /var/log/audit and /var/log/audit.log owned by root and 600 permissions. I've also removed and made an empty /var/log/audit directory when that did not we work either. I can start the service after boot up, but it is not coming up automatically even when configured by chkconfig. Any input or assistance would be appreciated.

I also get this after I attempt a restart...

Stopping auditd: [ OK ]
Error deleting rule (Operation not permitted)
Starting auditd: [ OK ]
The audit system is in immutable mode, no rules loaded

A tail of my /var/log/messages shows this...

Nov 23 16:45:18 hostname kernel: type=1302 audit(1290548718.524:73): item=1 name="/var/run/auditd.pid" inode=131143 dev=fd:01 mode=0100644 ouid=0 ogid=0 rdev=00:00 obj=user_u:object_r:var_run_t:s0
Nov 23 16:45:18 hostname kernel: type=1300 audit(1290548718.618:74): arch=c000003e syscall=87 success=no exit=-2 a0=7fff730b2f85 a1=7fff730b2f85 a2=2 a3=0 items=1 ppid=6243 pid=6248 auid=1111 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=pts1 ses=1 comm="rm" exe="/bin/rm" subj=user_u:system_r:unconfined_t:s0 key="delete"
Nov 23 16:45:18 hostname kernel: type=1307 audit(1290548718.618:74): cwd="/"
Nov 23 16:45:18 hostname kernel: type=1302 audit(1290548718.618:74): item=0 name="/var/run/auditd.pid" inode=131073 dev=fd:01 mode=040755 ouid=0 ogid=0 rdev=00:00 obj=system_u:object_r:var_run_t:s0
Nov 23 16:45:18 hostname kernel: type=1300 audit(1290548718.620:75): arch=c000003e syscall=87 success=yes exit=0 a0=7fff9b776f81 a1=7fff9b776f81 a2=2 a3=0 items=2 ppid=6243 pid=6249 auid=1111 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=pts1 ses=1 comm="rm" exe="/bin/rm" subj=user_u:system_r:unconfined_t:s0 key="delete"
Nov 23 16:45:18 hostname kernel: type=1307 audit(1290548718.620:75): cwd="/"
Nov 23 16:45:18 hostname auditd[6260]: Started dispatcher: /sbin/audispd pid: 6262
Nov 23 16:45:18 hostname audispd: af_unix plugin initialized
Nov 23 16:45:18 hostname audispd: audispd initialized with q_depth=80 and 1 active plugins
Nov 23 16:45:18 hostname auditd[6260]: Init complete, auditd 1.7.17 listening for events (startup state enable)

Change the /var/log/audit/ directory to 750 so that auditd can rw the audit.log file.
Then you can use auditctl to modify /etc/audit/audit.rules.

Changed the permissions like you said, the audit.log was already created by the time I got back yesterday though. Reboot the system to see if auditd would come up on it's own and it was not running.

[host**** ~]# service auditd status
auditd is stopped
[host**** ~]# service auditd restart
Stopping auditd: [FAILED]
Starting auditd: [ OK ]

I notice the following in my /var/log/messages from the last 20 lines since the last time I tested.

Nov 24 08:48:07 hostname**** kernel: type=1112 audit(1290606487.506:22): user pid=6090 uid=0 auid=1111 subj=system_u:system_r:unconfined_t:s0-s0:c0.c1023 msg='uid=1111: exe="/usr/sbin/sshd" (hostname=apgrb7atg46458c.nae.ds.army.mil, addr=192.168.5.21, terminal=/dev/pts/1 res=success)'
Nov 24 08:48:31 hostname**** kernel: type=1100 audit(1290606511.586:23): user pid=6117 uid=1111 auid=1111 subj=user_u:system_r:unconfined_t:s0 msg='PAM: authentication acct="root" : exe="/bin/su" (hostname=?, addr=?, terminal=pts/1 res=success)'
Nov 24 08:48:31 hostname**** kernel: type=1101 audit(1290606511.586:24): user pid=6117 uid=1111 auid=1111 subj=user_u:system_r:unconfined_t:s0 msg='PAM: accounting acct="root" : exe="/bin/su" (hostname=?, addr=?, terminal=pts/1 res=success)'
Nov 24 08:48:31 hostname**** kernel: type=1105 audit(1290606511.595:25): user pid=6117 uid=1111 auid=1111 subj=user_u:system_r:unconfined_t:s0 msg='PAM: session open acct="root" : exe="/bin/su" (hostname=?, addr=?, terminal=pts/1 res=success)'
Nov 24 08:48:31 hostname**** kernel: type=1103 audit(1290606511.595:26): user pid=6117 uid=1111 auid=1111 subj=user_u:system_r:unconfined_t:s0 msg='PAM: setcred acct="root" : exe="/bin/su" (hostname=?, addr=?, terminal=pts/1 res=success)'
Nov 24 08:48:54 hostname**** auditd[6179]: Started dispatcher: /sbin/audispd pid: 6181
Nov 24 08:48:54 hostname**** kernel: type=1305 audit(1290606534.103:27): audit_pid=6179 old=0 by auid=1111 subj=user_u:system_r:unconfined_t:s0
Nov 24 08:48:54 hostname**** audispd: af_unix plugin initialized
Nov 24 08:48:54 hostname**** audispd: audispd initialized with q_depth=80 and 1 active plugins
Nov 24 08:48:54 hostname**** auditd[6179]: Init complete, auditd 1.7.17 listening for events (startup state enable)
[root@vdl-dev-db01 ~]#

You still have to manually start auditd.. hrmmm...
As a sanity check, is the runlevel to which the system boots one of the runlevels listed in chkconfig --list | grep auditd?

/var/log/messages will show additional auditd events recorded after auditd tried to automatically start...
Between the events "(startup state enable)" and "audit daemon is exiting" should (could, would, hopefully) be recorded the reason(s) why the auditd is exiting.