I was selecting all the files in the minecraft folder, right clicking, selecting compress, and specifying minecraft.jar. I'm not sure what they are using on the backend, but it makes corrupt jar files.
I installed fastjar and compressed the minecraft.jar file from a terminal and minecraft started up with no issues.