There is 2 different cause for this issue.
1) Perhaps you are trying to upload the whole theme package zip file (which contain the PSD, Licence, Theme, etc..), instead of only the theme zip file.
If that's the case, make sure you unzip the theme package zip file on your computer, then check if there is a /Theme/ folder. If so, make sure you are uploading the theme zip file that is located in that theme folder.
2) If you are installing your theme from the WordPress theme installer, but get a message that says “Are you sure you want to do this?”, most likely your web server is configured with PHP settings that are too low to allow the theme ZIP file to upload. Specifically, PHP is configured to a maximum file upload size limit at 8 megabytes or less. The theme ZIP is currently about 34 megabytes in size which is mainly due to the included plugins and all the demo content. Thus, the web server is rejecting the upload. WordPress is giving you a rather ambiguous message in response.
This is not a theme fault or bug.
There two ways to solve this problem.
1. You can either get your web host to increase your PHP limits. You will need to talk to them or
2. You can upload your theme via an FTP client. Please read this article for more info: http://codex.wordpress.org/Using_Themes#Adding_New_Themes_Manually_.28FTP.29
Recommended PHP configuration limits are as follows:
max_execution_time 600
memory_limit 256M
post_max_size 48M
upload_max_filesize 48M
You can verify your PHP configuration limits by installing a simple plugin called WordPress phpinfo().