Well, after reading the following article, I figured the case Paul Hiles makes is not bad. Not every one wants or needs DI, and granted, in many cases moving from a "IoC Container used as a Service Locator" solution to a "real dependency injection" solution might just be not worth it, I believe that it's a better structure, especially if you're writing from scratch.
I'm not writing from scratch, and in fact, even bringing the software I worked on from "everything's coupled with everything's else" to "everyone knows just the one Service Locator as a global thingy" was a huge step towards an easier to read, testable code. Still, I'm looking forward to making the code even better by making all of the classes decoupled from the SL, except for the "points of entry" since I'm working on Web solutions.
Bottom line: read the article, decide if it's right for your situation - and write better code :)