You can disable the referrer check in the control panel, which I would higly advise against as it'll allow any script or url to post (including spammers using malformed clients).
This issue at hand can come from more than just firewalls...
1. Firewalls
2. Anti-Virus Programs (and Suites)
3. Internet Security tools
A couple I've heard of the problem with:
1. Zone Alarm, both free and pro.
2. Norton (aka Symantec) Internet Security
3. Norton (aka Symantec) AntiVirus
There should be an option in the appropriate program to disable it from disabling (or not forwarding) the refferral address.