The one problem with constructor injection is – even if clearly to be preferred – that one might end with a constructor with a dozen or more parameters. The constructor becomes harder to use. Parameters might get confused (if they don't have strict type hints, or adjacent types are the same). Setting up additional test cases is a pain because of all the services that need to be mocked and injected, but don't matter for the particular test case. A situation like this hints at a higher-level design issue: A service that needs so much stuff to be injected probably does way to many unrelated things, and should be broken up.
With this out of the way my personal rule of thumb is a pretty strict "dependency injection at construction time". But there is one exception: loggers. See, a logger does not really change the behavior of a service. It is merely a side-effect if what the service does additionally creates log entries – or not. Even if the logger is changed mid-way, nothing happens.
I still prefer constructor injection, even for loggers. But if the constructor is already quite big (let's say 4 or more arguments), or I want to temporarily add logging to an existing class, I avoid making the constructor more complicated. A setLogger method that defaults to a NullLogger if not called (super useful in test situations) is easy to add – and to remove.