Who is your webhost?
I had the exact same problem with a fresh new install of WordPress, so people said it was the PHP version. I was using a free webhost (000webhost.com) running PHP 5.2.17. I switched to another free host and the plugin installed without any problems. Now running PHP 5.3.24
