Ok, nice catch. Basically the problem is with file_context.XXX file. 

If exclude_dirs file is defined then the file_context.XXX is used for setfiles but substitution files are not used because of file_context.XXX.

(In reply to Miroslav Grepl from comment #1)
> Ok, nice catch. Basically the problem is with file_context.XXX file. 
> 
> If exclude_dirs file is defined then the file_context.XXX is used for
> setfiles but substitution files are not used because of file_context.XXX.

# setfiles /tmp/file_contexts.JovCpO6ONO /run

stat("/tmp/file_contexts.JovCpO6ONO", {st_mode=S_IFREG|0644, st_size=351111, ...}) = 0
open("/tmp/file_contexts.JovCpO6ONO.subs_dist", O_RDONLY) = -1 ENOENT (No such file or directory)

Easy fix could be something like

--- /sbin/fixfiles.old  2014-04-01 04:31:45.217000000 -0400
+++ /sbin/fixfiles      2014-04-01 06:07:02.273000000 -0400
@@ -137,6 +137,8 @@
     FC=/etc/security/selinux/file_contexts
 fi

+FC_SUB_DIST=${FC}.subs_dist
+
 #
 # Log to either syslog or a LOGFILE
 #
@@ -244,6 +246,8 @@
                logit "skipping the directory ${p}"
        done
 FC=$TEMPFCFILE
+/bin/cp -p ${TEMPFCFILE} ${TEMPFCFILE}.subs_dist &>/dev/null || exit
+/bin/cp -p ${FC_SUB_DIST} ${TEMPFCFILE}.subs_dist &>/dev/null || exit
 fi
 if [ ! -z "$RPMFILES" ]; then
     for i in `echo "$RPMFILES" | sed 's/,/ /g'`; do
@@ -266,7 +270,7 @@
     return
 fi
 echo "Cleaning up labels on /tmp"
-rm -rf /tmp/gconfd-* /tmp/pulse-* /tmp/orbit-* $TEMPFCFILE
+rm -rf /tmp/gconfd-* /tmp/pulse-* /tmp/orbit-* $TEMPFCFILE ${TEMPFCFILE}.subs_dist

 UNDEFINED=`get_undefined_type` || exit $?
 UNLABELED=`get_unlabeled_type` || exit $?

Wouldn't you want to copy the .subs file also?  In case the user had made any subs?

Oops. Yes, .subs file is also needed.

Updated patch which we have in rawhide.

 diff --git a/policycoreutils/scripts/fixfiles b/policycoreutils/scripts/fixfiles
-index 5c29eb9..75d3c8d 100755
+index 5c29eb9..097152f 100755
 --- a/policycoreutils/scripts/fixfiles
 +++ b/policycoreutils/scripts/fixfiles
 @@ -116,6 +116,7 @@ exclude_dirs() {
@@ -695712,6 +695712,36 @@ index 5c29eb9..75d3c8d 100755
  FORCEFLAG=""
  DIRS=""
  RPMILES=""
+@@ -137,6 +138,9 @@ else
+     FC=/etc/security/selinux/file_contexts
+ fi
+ 
++FC_SUB_DIST=${FC}.subs_dist
++FC_SUB=${FC}.subs
++
+ #
+ # Log to either syslog or a LOGFILE
+ #
+@@ -243,6 +247,10 @@ then
+       logit "skipping the directory ${p}"
+   done
+ FC=$TEMPFCFILE
++/bin/cp -p ${TEMPFCFILE} ${TEMPFCFILE}.subs_dist &>/dev/null || exit
++/bin/cp -p ${FC_SUB_DIST} ${TEMPFCFILE}.subs_dist &>/dev/null || exit
++/bin/cp -p ${TEMPFCFILE} ${TEMPFCFILE}.subs &>/dev/null || exit
++/bin/cp -p ${FC_SUB} ${TEMPFCFILE}.subs &>/dev/null || exit
+ fi
+ if [ ! -z "$RPMFILES" ]; then
+     for i in `echo "$RPMFILES" | sed 's/,/ /g'`; do
+@@ -264,7 +272,7 @@ if [ ${OPTION} != "Relabel" ]; then
+     return
+ fi
+ echo "Cleaning up labels on /tmp"
+-rm -rf /tmp/gconfd-* /tmp/pulse-* /tmp/orbit-* $TEMPFCFILE
++rm -rf /tmp/gconfd-* /tmp/pulse-* /tmp/orbit-* $TEMPFCFILE ${TEMPFCFILE}.subs_dist ${TEMPFCFILE}.subs
+ 
+ UNDEFINED=`get_undefined_type` || exit $?
+ UNLABELED=`get_unlabeled_type` || exit $?

commit 0d571e36878fb42fc9e024bc52a6fa439d707d2c
Author: Miroslav Grepl <mgrepl>
Date:   Fri May 16 15:14:37 2014 +0200

    Make fixfiles_exclude_dirs working if there is a substituion for the given directory

This bug is fixed. The problem found and described in BZ#1186640 will be addressed separately.

Since the problem described in this bug report should be
resolved in a recent advisory, it has been closed with a
resolution of ERRATA.

For information on the advisory, and where to find the updated
files, follow the link below.

If the solution does not work for you, open a new bug report.

https://rhn.redhat.com/errata/RHBA-2015-0477.html