Test your code like someone who would use it after reading the documentation. Do not test anything based on knowledge you have because you have written or read the code. You want to make sure that your code behaves as expected.
In the best case you should be able to use your tests as examples, doctests in Python are a good example for this.
If you follow these guidelines changing the implementation shouldn't be an issue.
Also in my experience it is good practice to test each "layer" of your application. You will have atomic units, which in itself have no dependencies and you will have units which depend on other units until you eventually get to the application which in itself is a unit.
You should test each layer, do not rely on the fact that by testing unit A you also test unit B which unit A depends on (the rule applies to inheritance as well.) This, too, should be treated as an implementation detail, even though you might feel as if you are repeating yourself.
Keep in mind that once written tests are unlikely to change while the code they test will change almost definitely.
In practice there is also the problem of IO and the outside world, so you want to use interfaces so that you can create mocks if necessary.
In more dynamic languages this is not that much of an issue, here you can use duck typing, multiple inheritance and mixins to compose test cases. If you start disliking inheritance in general you are probably doing it right.