Message: mkdir(): Permission denied

You can use the PHP function is_writable( $filename )
http://php.net/manual/en/function.is-writable.php
It should check if the current user may write to the passed filename, where filename may be a file or directory.

But if I was you, I would create a directory manually in your root directory and set the read/write permissions. Then use this directory as your base dir for the uploads. As this directory seems to be required for your application there is no need to set it via a PHP script

I have also tried to to comment out this script and create the folder manually as you said with permissions 0777, although is not so secure, but when I tried to upload a file the Upload library was displaying a message that the folder was not writable (!!!).

Also the uploads folder is my base dir for storing everything that a user uploads, like posts (posts dir is the base dir for all post images). In my uploads dir I'm also planning to store images for photo albums, so imagine that each user should have the ability to create album folders for uploading their photos in them.

So basically some sub-folders in the uploads directory would have to create them with PHP.

One additional thing I tried is to upload an image straight in my uploads directory, but I was still getting the same error.