If you have :
class Foo implements DoSomething {...}
class Bar implements DoSomething {...}
obj = new Foo();
obj.doSomething();
Everywhere in your code, once you want to change all instances of Foo to use instances of Bar, are you really going to do search/replace ?
If you have :
obj = DoSomethingFactory.create();
obj.doSomething();
Inside the DoSomethingFactory, you can return any object you want that implements the DoSomething interface.
By using a Factory, you have the control over all the objects that are created by it.
If you decide to change the way the Factory creates objects, the changes take effect immediately in the code that uses the Factory.