Gracias a Cluster por responder.
La cosa es que la solución fue de esta manera.
umask(0);
mkdir ($nuevodir, 0777);
El umask(0) permite que se puedan asignar los permisos 777, de lo contrario quedan predeterminados en 755 y como dijo Cluster:
...cuando creas un archivo por FTP .. el usuario es "X" .. cuando lo haces vía PHP (lo creas o lo subes por HTTP vía PHP) .. el usuario dueño de ese archvivo es "Y" .. por ende .. los permisos han de quedar "para todo usuario" para que X e Y puedan interactuar con el archivo (borrarlo, abrirlo .. etc).
Caso cerrado.
