Pero que permisos mirastes?
La rama superior a donde quieras crear un directorio debe tener permisos de escritura tanto al usuario que usa PHP (nobody o Apache u otro) como a tu usuario via FTP ..
Reivsa la función mkdir() en el manual de PHP
http://www.php.net/manual/en/function.mkdir.php
No sé si lo estaras usando .. pero el 2º parámetro de mkdir() tienes que indicar los permisos que le va a dar al directorio q vas a crear ...
Un saludo,