Location specific login problems?

Hi, I’m having problems with logins for some of my WordPress users.
I have 3 admin level accounts, all of which are accessible for me in the UK, on a number of different IP addresses. When these usernames / passwords are used by users in Germany and Australia, they get an error message saying cookies are disabled, when they aren’t.
Can anyone explain this?
I’ve looked through this page:
http://codex.wordpress.org/Login_Trouble
But nothing seems to explain my situation…

[No bumping, thank you.]