This is a WordPress error message that is misleading and it actually means that either the wrong file is being uploaded or the theme files packaged differently than expected as some authors may have zipped it for you, others do not.
You may need to compress the theme files. This file is often called the name of the theme within the zip you have downloaded. This file will contain the header.php, .css (stylesheet). Right click this file and choose to compress, then upload only that file.