The actual cause is not that the plugin isn't compatible, it's that the zip file as downloaded from CKEditor is really badly structured.
footnotes_1.1.0_0.zip, contains a folder called footnotes_1.1.0, which then contains another folder called CKEditorFootnotes-1.2.0, which then contains another folder called footnotes, which then contains the actual plugin code.
Do the following:
Drag the 'footnotes' folder out of the zip file
Then zip the footnotes folder (just dragged out) into a ZIP fil of its own
Upload away!!