Aparentemente con esto solucionas tu problema:
$oldumask = umask(0);
mkdir($nuevo_dir,0777);
umask($oldumask);
Todavía no entiendo muy bien lo de la máscara, pero ya lo probe y funciona.
Se habla al respecto en los ultimos comentarios de la pagina:
http://www.php.net/manual/es/function.mkdir.php