Okay, I'm going to try this one. If I screw something up or get something wrong by all means correct me.
Your e-mail client (outlook express) is trying to connect via Secure Sockets Layer or SSL. SSL is a security protocol used to ensure that messages are handled securely.
Outlook Express is configured to turn on SSL by default. This may not have been an issue with the PC by itself, but now that you've added a router to the mix it may be necessary to turn it off.
Tools>Accounts>Mail>Properties>Advanced
There is a "Server Port Numbers" division of the window and there are both an incoming and outgoing port number and a check box for SSL.
My advice, and by all means, I'm just some schmo on the Internet, would be to uncheck the incoming SSL connection box and see if that works. I wouldn't uncheck the outgoing box unless you've got problems sending e-mail through outlook express as well.
Hope that works for you.