This should be a comment - it's not an answer as there's not enough information in the question to identify the issue.
so it's not a permission issue, but an ownership issue.
Ownership is permissions - and if the directory is 0777 then the ownership is not the problem.
In addition to the visible file permissions, access to write a file is also subject to:
- SELinux constraints
- AppArmor contraints
- filesystem attributes
- filesystem acls
- whether the filesystem is mounted read-only
IIRC, except for the mount option, these are not enabled by default on Ubuntu - but have you checked?
Are there files inside this directory which are not writeable by the webserver uid?
What happens if you to write to the directory as the www-data user?
You did not say what the software producing the error is.