Warning: Your Magento folder does not have sufficient write permissions.

Si al entrar a Magento Connect, recibes este mensaje:
Warning: Your Magento folder does not have sufficient write permissions.

Entonces entra a la raíz del sitio donde está Magento y agregas el siguiente código (por ssh):
find . -type d -exec chmod 777 {} \;

Y fin!