Eu recentemente lutei com o mesmo problema no meu sistema Fedora 10. No meu caso, o culpado foi algum redirecionamento estranho que eu estava fazendo no Apache. Especificamente, eu uso um sistema de gerenciamento de conteúdo (Drupal, para ser exato) que dentro dele. O .htaccess inclui a seguinte lógica de redirecionamento para redirecionar arquivos ausentes para um script PHP:
# Rewrite URLs of the form 'x' to the form 'index.php?q=x'.
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_URI} !=/favicon.ico
RewriteRule ^(.*)$ index.php?q=$1 [L,QSA]
Faz sentido que o acima apenas afete o método PUT, já que nesse caso o REQUEST_FILENAME não existe.
Não ter a área WebDAV dentro da área do Drupal, o que parece ser uma restrição razoável, corrige o problema.
Além disso, acho que é provável que o SELinux resulte em um erro diferente, mas não é mencionado na discussão acima. Você tentou desativar o SELinux?