In my opinion, you should not create interfaces just for the purpose of unit testing. If you start adding code abstractions to please the tools, then they are not helping you to be more productive. The code you write should ideally serve a specific business purpose/need - either directly, or indirectly by making the code base easier to maintain or evolve.
Interfaces sometimes do this, but certainly not always. I find that providing interfaces for components is usually a good thing, but try to avoid using interfaces for internal classes (that is, code only used inside of the given project, regardless of whether the types are declared public or not). This is because a component (as in, a set of classes working together to solve some specific problem) represents a larger concept (such as a logger or a scheduler), which is something that I may feasibly want to replace or stub out when testing.
The solution (hat tip to Robert for being first in the comments) is to use a mocking framework to generate a compatible substitution type at run-time. Mocking frameworks then allow you to verify that the class being tested interacted correctly with the substituted dummy. Moq is as mentioned a snazzy choice. Rhino.Mocks and NMock are two other popular frameworks. Typemock Isolator hooks into the profiler and is among the more powerful options (allows you to substitute even non-virtual private members), but is a commercial tool.
It's no good making up rules for how much you should unit test. It depends on what you're developing and what your goals are - if correctness always trumps time-to-market and cost is not a factor then unit testing everything is great. Most people are not so lucky and will have to compromise to achieve a reasonable level of test coverage. How much you should test may also depend on overall skill level of the team, expected lifetime and reuse of the code being written, etc.