Probably your web-server user does not have permissions to create new files. I believe that WordPress caches comments on pages and posts for not logged users, so that only authenticated users get fresh comments list. When logged out user inputs a comment, the list gets updated with his comment too, which brings them the whole list (I tried that on my WP instance and yours, it works that way). Otherwise WP tries to get comments from a file, that it couldn’t create beforehand, resulting in have_comments() returning false.
So, if you provide write permissions for www-data or whatever else is called your web-server user, you will forget for the problem.
The whole thing is still a theory, as I won’t have access to my installation for about 10 days, but I strongly believe that this is the solution.