I had the same problem. Here is the solution.
You have to manually download and unzip the plugin. You will have a folder titled wp-youtube. Inside that folder is another folder also titled wp-youtube. Upload the second wp-youtube folder only.
Then Activate normally from your Plugins panel of your Dashboard. Hopefully the developer or WordPress will fix the folder structure problem because this is a wonderful plugin!
