The first file in the archive must be the mimetype
file. If it isn't, it won't pass validation. Also, that file must be stored uncompressed (in theory, anyway), and the directories themselves must not appear as separate entries, IIRC.
Getting this right usually requires either a command-line tool or an app that knows how to do it. For example, in OS X, you can usually get away with
zip -Xr9D ../filename.epub mimetype * -x .DS_Store