Did you put your test class in correct place in the folder structure, Martin?
Look at the table under "Flavors and build types support" on http://tools.android.com/tech-docs/unit-testing-support
It resolved the issue for me, but I had to move the test class (and create folders) manually - while Android Studio can generate the test suite automatically for you (Go to... Test, after right-clicking on the class header), it doesn't offer to put it in right location by default, so it can be confusing.
Also make sure to set Test Artifact to "Unit Tests" in Build Variants tab, but the official tutorial says that more explicitly so I assume that's not what you overlooked.
I understand your question was dated, but maybe someone stumbles upon it like I only just did struggling with this issue myself ;) And guys, remember - highest voted answers on StackOverflow that tell you to stick to Android tests and drop JUnit are obsolete now, Android Studio supports JUnit tests that run on your PC directly, as explained in the link I posted above. Of course they don't give you access to instrumentation - I use them to test my "pure" Java logic which is platform agnostic.