If you start with a valid kmz file created using either Google Earth or Custom Maps app, and don't change the size of the image (only doodle your own markings on it), the file created by standard zip tool should be OK as long as it has .kmz extension.
BTW, Custom Maps does not compress the kmz (zip) files it creates, as they typically contain only a large image file (which is already highly compressed) and a small kml file which doesn't take much space compared to the image file (so compression benefits are minimal). There is a tiny possibility that Custom Maps (or rather Android Java) would not be able to handle some compression algorithm applied by your zip tool, so you might want to try disabling compression with -0 option.
The other option is that after you edit the image (and possibly resize it), you just copy the image to your Android device and re-align it using Custom Maps.
Marko Teittinen