Java, like all languages, is a tool. I may not like Java, personally, but I'm sure that, in the right hands, it can produce reasonably good software. The same can be said for C/C++, C#, Perl, Ruby, FORTRAN, COBOL, or even Brainfuck. They've all got their pros and cons, but what it comes down to more often than not is the skills of the person behind the keyboard. A talentless hack is a talentless hack, it doesn't matter if he's using Baby's First Programming Language, or using freaking Assembly; either way, the code will suck, it won't run well, and it'll likely piss many users off.
Again, I've got my own personal reservations against Java, but I think Minecraft's primary performance issues aren't down to the virtual machine, but simply put, poor code. Sending the entire texture map to the graphics card roughly 20 times a bloody second is an example of bad code. Bad code can be improved, inefficiencies in the VM can, at times, be worked around, that's why there are patches and updates. You're not gonna release a 100% well-working product that's totally bug-free on release day, the time it'd take and money it'd cost would be prohibitive, to say the least. This means that, yes, sometimes, corners are cut, and kludges are made.
My primary problem with Mojang isn't that they use Java, but that they seem to be more focused on adding more content, instead of making the content that's there work better, and making the game a smoother play all around. Yeah, they do get around to it, but for every bit of new content you add, you add yet another source of problems, bugs, and inefficiencies. In essence, they're kinda doing it all backwards.