I was having the exact same problem when I tried to upload a custom theme that I had just purchased from a website. The cause of the error was because I was trying to upload a .zip file that also contained other support files and folders (such as photoshop files) instead of just the actual theme folder.
The theme that I was trying to upload was actually buried two folders deep in the zip file. To resolve the problem I simply unzipped the folder, located the actual theme folder in one of the subfolders. I zipped it and uploaded it to the server.
If you are not sure which is the correct folder, look for the folder containing files like these: index.php, header.php, footer.php
