I'm not sure what's the real reason here, but I guess that's because the new() method requires concrete type to choose implementation, and as trait T is parametrized by lifetime parameter, it needs some to complete the type instance. In the snippet above I used already defined lifetime parameter 'a defined for trait definition at hand. When I tried to use another lifetime by introducing it in method signature (fn test<'a>()) it didn't work as well. Lifetime placeholder '_ didn't work either, only concrete lifetime 'a known by the trait worked.
I think the problem is that the compiler seems to think you've made Self::Iter higher ranked by bounding it as having Item == Self::A. It seems to mistakenly think that Self is higher ranked in this context.