I'll tell you how this is fixed...
We stumbled across this issue as we developed a WordPress website ina subdomain, privately, for a client, before moving the completed WordPress website to it's new URL, and changing all the links etc over.
When we went to switch the privacy settings off, they kept not changing.
This is excacerbated by the WordPress SEO by Yoast plugin we use, which points to the OLD privacy settings page, which no longer works.
We had upgraded to the latest stable release between launching the test site and the live website. During the new WP (3.5 or 3.5.1) the Privacy options moved from:
In the second page, the privacy settings are at the bottom!
In addition to "unchecking" the option for privacy, we also added an unrestrictive Robots.txt file, and put in a valid, working sitemap.xml file (something Yoast's plugin does really well).
Hope this helps someone experiencing the same issue - we googled and came here... few things more frustrating than a support page with no answers (hint to OP - at least SAY what the solution was!).