I think images slightly smaller than 600x800 are probably best anyway, because they are not usually displayed full-screen. I was just repeating MobiPocket's own advice (600x800) for cover image size.
The limit on image file sizes is actually <63K, rather than <64K. I base this on two MobiPocket Forum threads:
jpg which are equal in size get different sizes and
Images in the ebook. So this might be your problem. In any case, one thing you could try (on one of the buggy 600x800 image .mobi files and a Windows desktop) is mobi2html and then mobigen -jpeg. If the mobigen version works on the Cybook then why? If not, then perhaps it isn't a html2mobi issue but a bug on the Cybook.