Just to clarify – you haven’t changed the Site URL and such in the Admin settings (if you don’t know what I’m talking about, then it’s probably a No)? I would delete the stuff you already have in the /themes folder on the server, and try again. There may be a conflict there…
This is weird. It’s never happened to me. I’ve had problems unzipping and just throwing it on the server, but when I actually login and go to Admin -> Appearance -> Themes -> upload and upload it, it always works. I’m sorry to hear this…