Sounds like a possible kernel bug. Which kernel is this?
I tried 2 standard Fedora kernels: kernel-2.6.11-1.1369_FC4 kernel-2.6.12-1.1398_FC4
Other related software: libselinux-1.23.10-2 selinux-policy-targeted-1.25.2-4
Did the problem begin to occur on a kernel upgrade or a policy upgrade, or a library upgrade?
I only tried it a few days ago, there was no policy or library update since then. Should I try older versions of kernel/library/policy/all of them?
Did you try it multiple times... are you sure there's a correlation between enforcing status and app working/not working?