Try to convert to string before replacing:
message = escape(message)
message = str(message).replace('\r\n','<br />').replace('\n','<br />')
or to unicode if you have unicode symbols in message:
message = unicode(message).replace('\r\n','<br />').replace('\n','<br />')