Try changing the permissions for the /uploads/ folder to 755.

Well, the way I usually install themes is to go in via FTP, and upload the theme's folder into the /wp-content/themes/ directory.  Reason for that, is that mucking around with the folders permissions too much might lead to security issues down the road.  So, that is at least alternative - I'm sure a few other WP users here might have some suggestions too.

KStark,

Let me know how you are doing with this issue.  I have been having the exact same problem.  Here are some diagnostics I have found concerning the issue.  The following is an excerpt from a site that had some good info

"This is a common error due to permissions. I got this error fixing a WordPress instalation on another host which, will remain unnamed, I did some research and while reading the solutions out there I was amazed to see the amount of posts asking people to chmod 777 their entire wp-content and wp-content/upload directory. Let me say this once: it’s never a good solution to chmod 777 an entire directory.

Let’s analyze the problem to better understand what’s going on. When you create directories either via FTP or via some other method, the directory is owned by the user that created that directory. So when you upload your Wordpress via FTP the directories are owned by your user. Then when we try to upload images via the WordPress admin we are uploading via a web page we are actually uploading via http, and items uploaded through http are owned by the Apache user, master of http. So when the Apache user tried to put a file in the folder owned by your user, Linux steps in and notes there is a permission problem. You cannot put content into a directory owned by another user and spits back the error:

The solution lies in the way your shared hosting server is setup, some hosting companies use default installations and other fine tune the servers and making them perform faster and work better for their clients. Servers should be configured so Apache runs as the same user as your user (a different one for each website), this means that your user and Apache are the same which resolves the permission issue."

And from another source I also found,

"Before you read further, please note A) these instructions are for *nix servers (typically Linux), not Windows servers, so ask your host which you have if you don’t know, B) you’ll need to ssh into your server  and run command line commands, and C) I have the very macho root  access to my Linux/Apache server, so I can run chown commands. Most hosts will disallow you root access, and you’ll simply have to ask your tech support to do this. That shouldn’t be a problem.

you want the ownership and permissions to look like this for these three important directories:

wp-content drwxr-xr-x (755)  user group
uploads drwxr-xr-x (755)  apache apache
themes drwxr-xr-x (755) user group

and PHP safe_mode is OFF

Let me know what happens and if you get your theme to run correctly.  I am trying to get a site update down for business asap also.

i can't install my new wordpress theme either. i also get an error message.
i installed the zip into wp theme, extracted it. it showed up at my wp admin themes.
when i activated it, i was re-directed to an error message page.
i tracked down, that i think i needed to upgrade my wp to 3.03, but when i went to upgrade,
it came back unsuccesful, due to my php was outdated.
i don't know how to update my php from 4. something to 5.0 which is what is required.
i used to upgrade wp thru fantastico, but i can't find fantastico anymore at this site.
i guess i have to call lunarpages---and have them explain to me how to upload a wp theme...
just ridiculous...why can't lunarpages quit changing things around all the time. it's already hard enough as it is.

The Fantastico stuff is a CPanel thing - and honestly I don't know why CPanel put the thing in there. It causes far more problems than it solves. 

How are you trying to upload to WordPress (using the WP-Admin panel to upload and install or using FTP to upload the files and then WP-Admin to install)? What is it that you are trying to install?

As for "other suggestions" - It's not always practical, but if I were in the situation of having issues with a Fantastico install of anything - I'd be considering taking Fantastico out of the equation and doing it manually.

So, of that file path, what part already exists? /home/ACCOUNT/public_html/ must of course exist (assuming you're on a Linux server). Does XXXXX/wp-content/uploads/ exist? Does 2012/ exist? You may need to create directories up through 2012/ manually, using the cPanel/LPCP file manager.

If the directories (up through 2012/) seem to exist already, who owns them and what are their permissions? Sometimes application installations or file transfer clients can give odd ownership to directories. Are yours the same owner as the rest of the WP directories and files? The same as public_html/? If not, tech support will have to chown them for you. If ownership is OK, are permissions 755? If someone tried to make them 777, you will be unable to write to them.

Run this cron job once:
or, if you have SSH command line access, you can run it from there.

It will list all your files, including the owner, permissions, and last update time.