Cannot upload themes. Error: “The uploaded file could not be moved to /var/www/wp-uploads/localhost/2011/10.”

From quick search of source for this error message, it is likely to be triggered by failed move_uploaded_file() function call, which is native PHP and not WordPress.

Documentation says that it has some restrictions, related to safe_mode and open_basedir so that might be your issue.

Since WP suppresses error output from this function with @ directive I’d try to emulate such file move or un-suppress error (as far as I know this is not possible natively, but possible with xdebug and possibly other debuggers).