Even with the TCK license, I think the major problem was licensing of the JVM.
Google wanted to make Android open source, but the JVM license requires the GPL, which Google and a lot of companies using it now won’t touch with a pole.
So they had to use more liberal license, like the one they use in most of their other projects and the only way to do that was to write their own new VM (this probably also allowed them to more easily tailor it for mobile use).
I don't think a GPL'd JVM would be a deal-breaker. It's at about the same level as Linux, probably less likely to be tweaked by device builders. Not having the classpath exception on the libraries would be a no go though.
If a distro doesn't pass the TCK, it can't be called Java.