If you login through ssh/ftp and create the directory, it will be owned by your login user. When PHP tries to chmod the directory, it is running as the web server user (usually "httpd", "apache", or "nobody"), and being not the owner of the directory it won't be able to chmod it. My guess is, that is what is happening.
Planetsim's example will work as long as the directory does not exist, because it will then be created by the web server and so will be owned by the web server user. At that point PHP should be able to do anything to it.