Please can you try to reproduce the problem with dnf-2.5+. It is available for rawhide, Fedora 26, or from our dnf-nightly repo for Fc24+ ("dnf copr enable rpmsoftwaremanagement/dnf-nightly")?
If the problem is reproducible with dnf-2.5+ please provide:
1. Run it with --debugsolver option and provide debugsolver data
2. Provide /etc/dnf/dnf.conf
3. Please provide exact version of dnf, libdnf, libsolv (rpm -q <argumets>)