perl-cleaner slot conflict when upgrading perl (5.16 -> 5.18)

If you tried upgrading from stable amd64 to ~amd64 or otherwise done a big update of perl, you probably hit this weird perl-cleaner slot conflict:

# perl-cleaner --all
!!! Multiple package instances within a single package slot have been pulled
!!! into the dependency graph, resulting in a slot conflict:

dev-lang/perl:0

  (dev-lang/perl-5.18.2:0/5.18::gentoo, installed) pulled in by
    =dev-lang/perl-5.18* required by (virtual/perl-IO-1.280.0:0/0::gentoo, ebuild scheduled for merge)
    ^              ^^^^^                                                                                                                                  
    dev-lang/perl:0/5.18=[-build(-)] required by (perl-core/version-0.990.800:0/0::gentoo, installed)
                 ^^^^^^^^                                                                                                              
    (and 7 more with the same problems)

  (dev-lang/perl-5.16.3:0/5.16::gentoo, ebuild scheduled for merge) pulled in by
    =dev-lang/perl-5.16* required by (virtual/perl-Package-Constants-0.20.0-r3:0/0::gentoo, installed)
    ^              ^^^^^                                                                                                                                  
    (and 6 more with the same problem)

This is bug #506616, and the solution is to run the following command:

perl-cleaner --all -- --backtrack=30