The site/blog has been around since 2004 and has about 4000 posts. I do have a site map, but it only indexes 500 of the urls.
I read in the Webmasters help section that "fails" happen because of site overload or redirection. Neither should be the problem in my case.
Does anyone have another idea?