4) Contatta il servizio hosting e chiedi se ci sono restrizioni particolari.

Ad ogni modo, mi sono trovato anch'io in una simile situazione: mkdir funzionante ma diritti non assegnati (su coppermine). Senza scomodare il servizio hosting ho risolto con comandi ftp via php:

codice:
//added by Andrea
if (isset($_GET['startdir'])) {
	$chmod = chmod("/public_html/coppermine/albums/".$_GET['startdir']."/", 0777);
	if (!$chmod) {
	  //CHMOD via FTP
	  $ftp_server = "tuosito.com";
	  $ftp_user_name = "username";
	  $ftp_user_pass = "password";
	  $conn_id = ftp_connect($ftp_server);
	  $login_result = ftp_login($conn_id, $ftp_user_name, $ftp_user_pass);
	  
	  // check connection
	  if ((!$conn_id) || (!$login_result)) {
	    echo "FTP connection has failed!";
		echo "Attempted to connect to $ftp_server for user $ftp_user_name";
        exit;
	  } 
	  else {
		$chmod_file = "/public_html/coppermine/albums/".$_GET['startdir']."/";
		$ftp_chmod = ftp_chmod($conn_id, 0777, $chmod_file);
		if (!$ftp_chmod) {
		  $last_way = ftp_site($conn_id, sprintf('CHMOD %o %s', 0777, $chmod_file));
		}
	    // close the connection
	    ftp_close($conn_id);
	  }
   }    
}
//
Adattalo alle tue necessità (correggi path e user/pwd per l'ftp)