My understanding is that FC4 only enforces targeted policy which only protectes a few daemons and amanda is not one of them. So amanda should work fine even when selinux (default targeted policy) is enabled.
One data point, I enabled SELinux's targeted policy:

[[email protected] ~]$ sestatus
SELinux status: enabled
SELinuxfs mount: /selinux
Current mode: permissive
Mode from config file: permissive
Policy version: 18
Policy from config file:targeted

Policy booleans:
allow_ypbind inactive
dhcpd_disable_trans inactive
httpd_disable_trans inactive
httpd_enable_cgi active
httpd_enable_homedirs active
httpd_ssi_exec active
httpd_tty_comm inactive
httpd_unified active
mysqld_disable_trans inactive
named_disable_trans inactive
nscd_disable_trans inactive
ntpd_disable_trans inactive
portmap_disable_trans inactive
snmpd_disable_trans inactive
squid_disable_trans inactive
syslogd_disable_trans inactive
winbind_disable_trans inactive
ypbind_disable_trans inactive

amanda( 2.5.0b1) backup and recover work fine.
Has anyone used amanda on SELinux when STRICT policy is enforced?