Wierd probem here, small deployment which was working.

Users are reporting that they can't send a new mail message ( it ends up with the red cross). If they reply to an existing mail the it works fine.

Very odd since it was working and stopped a few days ago. Reboots don't help and the connection seems fine since they are receiving mail and replying to these okay.

Any ideas?

Open one of the failed emails and get the Message Status. That will tell you why it's failing.