I'm on my third copy. Might mention I'm using Ubuntu with the newest Java update as well. Nothing against them game, it's awesome, but the bugs bug me.
I use minecraft on a ubuntu 10.04, with java version 1.6.0_25, and I don't have any such problem. Unless I use bad password or my connection gets into trouble. Then I can use the offline version, which outputs this message.
Guilty until proven innocent. I'd rather them not output this message at all. It's a bit discouraging as a paying customer to see this as I usually only play the game offline; due to my incredible slow Internet speed. It's one of the better "DRM"s, but could use work.
My son plays it on my (admittedly underpowered) PC running Ubuntu 10.10, and it's rather crash-prone. I suspect it might be due to an issue with the graphics driver.