audit-libs-python package only provides Python 2 bindings that are not importable in Python 3. AFAICS policycoreutils-python3 works fine even without using any audit code, so it should be ok to just drop audit-libs-python dependency. Please do this in F22 and rawhide, so that we can successfully implement https://fedoraproject.org/wiki/Changes/Python_3_Migration_Improvements
This is just a cosmetic change which won't probably solve your problem.
The thing is that policycoreutils-python can't be replaced be policycoreutils-python3 now. Sadly, policycoreutils-python3 port seems to be incomplete and unusable in this moment. There are two missing parts:
- sepolgen module is not ported to python3
I've started to port the code in my personal github branch  but it's not ready yet as 'make test PYTHON=python3' still fails
- audit2allow and other tools imports seobject which uses audit.audit_log_semanage_message to log ROLE related messages
policycoreutils-2.3-16.fc22 has been submitted as an update for Fedora 22.
* should fix your issue,
* was pushed to the Fedora 22 testing repository,
* should be available at your local mirror within two days.
Update it with:
# su -c 'yum update --enablerepo=updates-testing policycoreutils-2.3-16.fc22'
as soon as you are able to.
Please go to the following url:
then log in and leave karma (feedback).
policycoreutils-2.3-16.fc22 has been pushed to the Fedora 22 stable repository. If problems still persist, please make note of it in this bug report.