I can reproduce this bug exactly as described.

  I downgraded audit (and audit-lib, pam, and pam-devel to satisfy dependencies)
to the original versions using rpm -Uvh --oldpackage.  The shutdown errors went
away.  Then I upgraded the packages back to the original versions using rpm -Fvh
(not up2date).  The update immediately gave the following errors.  Hence the
2-package bug and the audit errors are probably separate bugs.

Jul 18 09:30:14 localhost auditd[1824]: The audit daemon is exiting.
Jul 18 09:30:15 localhost kernel: audit: *NO* daemon at audit_pid=1824
Jul 18 09:30:15 localhost kernel: audit(1121693415.539:340917): arch=40000003
syscall=102 success=no exit=-22 a0=b a1=bf9de090 a2=80510f8 a3=0 items=0
pid=2670 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0
comm="auditctl" exe="/sbin/auditctl"
Jul 18 09:30:15 localhost kernel: audit(1121693415.539:340917):
saddr=100000000000000000000000
Jul 18 09:30:15 localhost kernel: audit(1121693415.539:340917): nargs=6 a0=3
a1=bf9e01ec a2=10 a3=0 a4=bf9e2388 a5=c
Jul 18 09:30:15 localhost kernel: audit(1121693415.640:340932): SELinux: 
unrecognized netlink message type=1009 for sclass=49
Jul 18 09:30:15 localhost kernel:
Jul 18 09:30:15 localhost kernel: audit(1121693415.640:340932): arch=40000003
syscall=102 success=no exit=-22 a0=b a1=bf9de070 a2=80510f8 a3=0 items=0
pid=2670 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0
comm="auditctl" exe="/sbin/auditctl"
Jul 18 09:30:15 localhost kernel: audit(1121693415.640:340932):
saddr=100000000000000000000000
Jul 18 09:30:15 localhost kernel: audit(1121693415.640:340932): nargs=6 a0=3
a1=bf9e01cc a2=10 a3=0 a4=bf9e2368 a5=c
Jul 18 09:30:15 localhost kernel: audit(1121693415.659:341310): SELinux: 
unrecognized netlink message type=1009 for sclass=49
Jul 18 09:30:15 localhost kernel:
Jul 18 09:30:15 localhost kernel: audit(1121693415.659:341310): arch=40000003
syscall=102 success=no exit=-22 a0=b a1=bfcc4010 a2=80510f8 a3=0 items=0
pid=2677 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0
comm="auditctl" exe="/sbin/auditctl"
Jul 18 09:30:15 localhost kernel: audit(1121693415.659:341310):
saddr=100000000000000000000000
Jul 18 09:30:15 localhost kernel: audit(1121693415.659:341310): nargs=6 a0=4
a1=bfcc616c a2=10 a3=0 a4=bfcc8308 a5=c
Jul 18 09:30:15 localhost auditd[2674]: Init complete, auditd 0.9.15 listening
for events

  Forgot to mention that the update using rpm -Fvh resulted in just one version
of each package being installed, as expected.

This is not really a bug. Its harmless. What is happening is the audit system is
trying to remove any file system auditing watches so that unmount can proceed
cleanly. However, the file system watch patches for the kernel are still not
quite accepted upstream and consequently not compiled into the FC kernels. This
means it is making calls that SE Linux doesn't understand. SE Linux is what's
reporting the audit messages.

This should work itself out when the file system watch kernel patches are put in
and SE Linux policy updated.

  In that case, the only remaining issue here is the double install of audit, so
this should probably be considered a duplicate of bug #161038, which should be
moved from NetworkManager to up2date (and maybe the title changed to something
like "up2date can cause packages to be installed twice").

*** Bug 164733 has been marked as a duplicate of this bug. ***

The audit daemon is not setting audit pid to 0 as it shuts down. This may be
fixed in version 1.0.3 - which is under development. The fix will get rid of the
NO Audit Daemon message, but all the others will still be there. 

Using all the currently released software, it should be down to only a hwclock
message.

Bug 165611 was opened to document the hwclock/initscripts problem. A fix was
placed in audit-1.0.2-2 to set auditd_pid to 0 in the kernel on normal shutdown.
I think this is is now solved. Thanks for reporting the bug.