Sun had a mobile platform at the time, J2ME. If you wanted to use Java on mobile, it had to be J2ME. There was no option back then to just pay money and pick'n'choose which bits of Java you wanted. In fact there still isn't, the Java guys are zealous about compatibility.
And J2ME was in turn a slow, multi-vendor, standards oriented kind of thing with multiple implementations. It was (a) very limited, (b) very buggy, (c) very poor developer UX. The issue wasn't Java itself but rather the huge variety of bugs and missing APIs between different phones. See the issues Android faced with fragmentation and multiply it by a million. In fact it was an attempt to fight fragmentation that led Sun to take the hard-line "our way or the high way" approach!
Additionally, J2ME was not open source but Google or rather Andy Rubin felt strongly that Android had to be open source under non-GPL licenses because mobile vendors hated the GPL. They could just about tolerate Linux but that was the limit. So Google was going to go to Sun and say, hey, please release one of your own profitable Java products under an open source license, so we can make more money out of Google Maps? No way.
Could Google have made Android using J2ME? Maybe. Perhaps? But it'd have been a huge ball and chain around their ankles and Android would have been radically different, likely different enough to have killed it. For instance J2ME had a simple GUI library but it was limited by the need to run on feature phones. They'd have never been able to make it as advanced as the Android GUI toolkit was, and competing with the iPhone? Forget it.
To some extent this situation was inevitable. From a technical perspective using the Java platform worked out very well for Android. But given Sun's business model at the time and the history of J2ME there was no way to take it to the next level. In hindsight we can say that Google could have replaced the entire revenue stream of J2ME, but what company wants to replace a many-vendor many-customer ecosystem with a single revenue source? Nobody would do that!