Try using a FTP program : search download.com for example, theres hundreds, some free some not, anyway these FTP programs allow you to upload Files & Folders from your desktop, you simple enter in your (your hosting details) site url, your username & password. Hay presto.

Anyway getting back to your problem, you up loaded the new theme, then what did you do. ?

Did you goto your admin panel and select the new theme or ?

Just some further question, if you cant upload folders & stuff, how did you get your site there in the first place ? do you have a nuke site ? iam just asking but you do know these themes are just skins for nuke sites, ie: you need a site first.