This issue is covered here many many times; it boils down to either:
1. Virus Scanner
2. Internet Security Suite
3. Firewall
One of the above is blocking the referrer variable from populating from their machine.
You could stunt your security by turning this check off; it's in General Settings; I myself don't find this as a valid fix.
