Error when uploading attachments

I have just finished moving from a shared host to a managed VPS. Everything seems to have gone smoothly apart from one problem, attachments now won't upload.

This is the error in the admin error log:

ErrorException: move_uploaded_file(public_html/internal_data/attachments/0/ [<a href='function.move-uploaded-file'>function.move-uploaded-file</a>]: failed to open stream: Permission denied - library/XenForo/DataWriter/AttachmentData.php:203
It gets this error on every single upload no matter how large/small file size is.
Any ideas?

Cheers, Ace.