Olika mailservrar har olika toleransnivåer och även om du skickat ut nyhetsbrev innan betyder det inte att du använt svenska tecken i rubriken. Av erfarenhet misstänker jag starkt att du inte kodar rubiken enl. standard, därav felet.
Ett tips (om du använder PHP):
http://www.php.net/manual/en/functio...mimeheader.php