Email Sending Problem

Not a total surprise but I'm having some problems with email sending. On my system it works fine but some testers are having problems.

Can enyone help with this one?

Here's part of the debuglog output of a failed send:

OPENING TCP STREAM:smtp.online.no(PORT:25)
COMPUTER SAYS:220 mail44.nsc.no ESMTP Sendmail 8.12.11/8.12.11; Thu, 7 Apr 2005 18:59:28 +0200 
SENDING: HELO Naked War
COMPUTER SAYS:501 5.0.0 Invalid domain name

Compared to mine (succesful send):

OPENING TCP STREAM:smtp.ntlworld.com(PORT:25)
COMPUTER SAYS:220 ESMTP server ready
SENDING: HELO Naked War
COMPUTER SAYS:250 aamta01-winn.mailhost.ntl.com

The server thinks there is a syntax error in HELO Naked War. Maybe this document has some relevance...
http://slett.net/spam-filtering-for-mx/smtpchecks.html

Cheers for that link. Looking into it.