Why does a trait on a reference raise "cannot borrow as mutable because it is also borrowed as immutable" when a trait on an object does not?

The problem is with the way you've declared the lifetime you want to use:

fn clear_non_empty<'a, Collection>(collection: &'a mut Collection)
where
    &'a mut Collection: Clear,
    &'a Collection: IsEmpty,
{
    if !collection.is_empty() {
        collection.clear()
    }
}

You've given clear_non_empty a lifetime parameter. This means that it's a lifetime the caller can pick, and also that it outlives the entire clear_non_empty function call (because in nearly all cases that's a practical requirement for the function to be able to use the lifetime). But that's not what you need — you need two lifetimes (one for calling is_empty() and one for calling clear()) that do not overlap, so that they do not conflict.

Lifetime parameters can't do this, but you don't actually need a lifetime parameter. What clear_non_empty needs to know is: “if I take a borrow of Collection, will it implement Clear?” And Rust in fact has a syntax for this (having the somewhat esoteric name of “higher-rank trait bounds”, or HRTB):

fn clear_non_empty<Collection>(collection: &mut Collection)
where
    for<'a> &'a mut Collection: Clear,
    for<'b> &'b Collection: IsEmpty,
{
    if !collection.is_empty() {
        collection.clear()
    }
}

(Syntax note: for<'a> is introducing a lifetime for the following bound only, so each bound could use the same name; I wrote for<'b> just to highlight that they are distinct.)

Notice that the collection parameter no longer has a lifetime — that's also important, because when we call collection.clear() we're not passing the reference we got to it, we're passing an implicit reborrow with a shorter lifetime, so that it doesn't conflict with the borrow for is_empty. The new lifetime annotations accurately reflect what we're doing with collection, rather than requiring longer lifetimes.

The reason you don't have to worry about this when writing traits like trait Clear { fn clear(&mut self); } is because the lifetime quantification — "for any lifetime 'a, we can clear &'a mut Self" — is implicit in the function signature of Clear::clear, which could be written explicitly as fn clear<'a>(&'a mut self);. it is normal that functions from a trait can be called with lifetimes shorter than any constraint on the implementor of the trait.

I thought this could perhaps be solved by using separate lifetimes for IsEmpty and Clear, like so:

trait IsEmpty {
    fn is_empty(self) -> bool;
}

trait Clear {
    fn clear(self);
}

fn clear_non_empty<'is_empty, 'clear, Collection>(collection: &'clear mut Collection)
where
    Collection: 'clear + 'is_empty,
    &'clear mut Collection: Clear,
    &'is_empty Collection: IsEmpty,
{
    if !collection.is_empty() {
        collection.clear()
    }
}

However this still runs into:

error: lifetime may not live long enough
  --> src/lib.rs:15:9
   |
9  | fn clear_non_empty<'is_empty, 'clear, Collection>(collection: &'clear mut Collection)
   |                    ---------  ------ lifetime `'clear` defined here
   |                    |
   |                    lifetime `'is_empty` defined here
...
15 |     if !collection.is_empty() {
   |         ^^^^^^^^^^^^^^^^^^^^^ argument requires that `'clear` must outlive `'is_empty`
   |
   = help: consider adding the following bound: `'clear: 'is_empty`

Here we see that the compiler is convinced that 'clear must outlive 'is_empty, while instead we require that these lifetimes do not overlap. But if these lifetimes do not overlap, then how can we turn our mutable reference into an immutable one for the duration of the call to is_empty?

It could be we are running into a limitation of the borrow checker, but let's give it some help and try to separate 'clear and is_empty a bit more:

trait IsEmpty {
    fn is_empty(self) -> bool;
}

trait Clear {
    fn clear(self);
}

fn clear_non_empty<'is_empty, 'clear, 'input, Collection>(collection: &'input mut Collection)
where
    'input: 'clear + 'is_empty,
    &'clear mut Collection: Clear,
    &'is_empty Collection: IsEmpty,
{
    if !collection.is_empty() {
        collection.clear()
    }
}

It does not help:

error[E0502]: cannot borrow `*collection` as mutable because it is also borrowed as immutable
  --> src/lib.rs:16:9
   |
9  | fn clear_non_empty<'is_empty, 'clear, 'input, Collection>(collection: &'input mut Collection)
   |                    --------- lifetime `'is_empty` defined here
...
15 |     if !collection.is_empty() {
   |         ---------------------
   |         |
   |         immutable borrow occurs here
   |         argument requires that `*collection` is borrowed for `'is_empty`
16 |         collection.clear()
   |         ^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

At this point I am pretty confident that this is indeed a borrow checker limitation, although I am not sure whether this is a bug or a feature.

If I were you I would open an issue on the Rust repository to get some expert help.