As a first rule of thumb, I prefer abstract classes over interfaces, based on the .NET Design Guidelines. The reasoning applies much wider than .NET, but is better explained in the book Framework Design Guidelines.
The main reasoning behind the preference for abstract base classes is versioning, because you can always add a new virtual member to an abstract base class without breaking existing clients. That’s not possible with interfaces.
There are scenarios where an interface is still the correct choice (particularly when you don’t care about versioning), but being aware of the advantages and disadvantages enables you to make the correct decision.
So as a partial answer before I continue: Having both an interface and a base class only makes sense if you decide to code against an interface in the first place. If you allow an interface, you must code against that interface only, since otherwise you would be violating the Liskov Substitution Principle. In other words, even if you provide a base class that implements the interface, you cannot let your code consume that base class.
If you decide to code against a base class, having an interface makes no sense.
If you decide to code against an interface, having a base class that provides default functionality is optional. It is not necessary, but may speed up things for implementers, so you can provide one as a courtesy.
An example that springs to mind is in ASP.NET MVC. The request pipeline works on IController, but there’s a Controller base class that you typically use to implement behavior.
Final answer: If using an abstract base class, use only that. If using an interface, a base class is an optional courtesy to implementers.
Update: I no longer prefer abstract classes over interfaces, and I haven’t for a long time; instead, I favour composition over inheritance, using SOLID as a guideline.
(While I could edit the above text directly, it would radically change the nature of the post, and since a few people have found it valuable enough to up-vote it, I’d rather let the original text stand, and instead add this note. The latter part of the post is still meaningful, so it would be a shame to delete it, too.)