It turns out that if you have enabled mod_rewrite on the server and you are actually doing any url re-writing for the site under which WebDAV is running, then you will not be able to create new directories or files via WebDAV.
To fix this, all you have to do is disable the mod_rewrite when connected via the dav protocol. The mod_rewrite will still be active when browsing the site.
Just add RewriteEngine off to the Location node of the sites-available file and then reload Apache. Here is an example:
<Location /webdav/prj>
DAV On
AuthType Digest
AuthName "prj@my.domain.com"
AuthUserFile /webdav/digestpasswd.dav
Require valid-user
php_value engine off
RewriteEngine off
</Location>
Then reload apache:
sudo service apache2 reload
Provided that your directory permissions of the WebDAV directory is set correctly (the user under which Apache is running needs to be the owner and have write permissions) you should now be able to create new directories and files.