We have a Concrete5 site that we built last year. It has been running fine up till 3 months ago when our entire database and all of the files got accidentally deleted from our webhost. We were able to restore everything from backups that were made three (3) days before. I then ironed out the initial issues that were created from the restore by updating to 5.6.1.1. A month later while working on our site I realized that the File Manager was no longer accepting uploads. It currently returns the error:
"Unable to copy file to storage directory. Please check permissions on your upload directory and ensure they can be written to by your web server."

I have tried recursively setting all permissions on the files directory to 775 and 777, neither of which worked. Php safe mode is off. I'm running out of ideas. I need to get this back up as we have things to update on our site. Does anyone have any experience with this? Any suggestions would be appreciated.

Thanks,
Caleb A.