I've done everything listed in the codex (checking the site URI, checking firewalls, extensions, other software) and referrers are definitely being sent (according to RefControl).
I recently upgraded to 2.0.2 onto a new server (and new domain name) and everything was fine. I initially got the error when I tried to change the name of my blog, but after configuring my firewall it was fine. But now when I try and save a post the error comes up again. I thought it could have been .htaccess, so I edited the file back to when it worked, and also removed the file altogether, and also switched PHP versions from 5 to 4... and still nothing.