Conflicting trait implementations even though associated types differ

You can accomplish this pattern by defining a second trait that does the actual work, and is implemented for (Counter<'a, T>, <T as Deref>::Target), and have the Counter trait call out to that implementation.

I don't think that was very clear, but I think an example can illustrate well. Using Shepmaster's shorter example for clarity, we would go from this:

use std::ops::Deref;

trait Foo {}

impl<T> Foo for T
    where T: Deref<Target = u8>
{}

impl<T> Foo for T
    where T: Deref<Target = bool>
{}

fn main() {}

to this:

use std::ops::Deref;

trait Foo {}
trait InnerFoo {}

impl<T> Foo for T
    where T: Deref,
          (T, <T as Deref>::Target): InnerFoo
{}

impl<T> InnerFoo for (T, u8)
{}

impl<T> InnerFoo for (T, bool)
{}

fn main() {}

Unfortunately this is not implemented in the language yet.

There's this tracking issue: rust-lang/rust#20400.

An RFC rust-lang/rfcs#1672 was also proposed to solve this problem but was then postponed waiting for Chalk integration which will make it easier to implement.

In the meantime, you'll have to use the workaround proposed above.