Recently bought new computer and set up Outlook Express as email. Am receiving email fine, but when sending an email I get the following message:

The message could not be sent because one of the recipients was rejected by the server. Acct:pop.embarqmail.com', server:'smtp.embarqmail.com', protocol:smtp. Server Response: '554 Authentication Failed, must login'. Port 25, Secure (SSL): No, Server Error: 554, error number 0x800CCC79.

Anyone have an idea, please?

Change the properties of the connection to authenticate when you send mail.

As in, the tickbox at the bottom of the box as shown here, obviously don't change your details to match this, just the one tick-box needed:
http://www.denick.net/auth.htm