Do you get any error messages if you don't use the "no_output" parameter with xp_cmdshell? i.e. run the xp_cmdshell by omitting the no_output parameter.

It could be that the account the SQL Server service is running under does not have access rights to create the folder...

Forgot to add - is there any reason to use xp_cmdshell and do this task via SQL? I would prefer to use .SQL CLR instead of xp_cmdshell...