Downside of extension methods: clients pre-C#3/VB9 won’t be able to use it as easily.
That’s about it as far as I’m concerned – I think the interface-based approach is significantly nicer. You can then mock out your dependencies nicely, and everything is basically less tightly coupled. I’m not a huge fan of class inheritance unless it’s really about specialization 🙂
EDIT: I’ve just thought of one other benefit which might be relevant. It’s possible that some of the concrete implementations could provide more optimized versions of some of the general methods.
Enumerable.Count is a good example of this – it explicitly checks whether the sequence implements IList or not, because if it does it can call Count on the list instead of iterating through the whole sequence. If IEnumerable<T> had been an abstract class with a virtual Count() method, it could have been overridden in List<T> rather than there being a single implementation which knows about IList explicitly. I’m not saying this is always relevant, nor that IEnumerable<T> should have been an abstract class (definitely not!) – just pointing it out as a small possible disadvantage. That’s where polymorphism really would be appropriate, by specializing existing behaviour (admittedly in a way which only affects performance instead of the result).