Give more information.
For example, what was the setup when it did work? Was it another Mac?
Is this the first time you've ever set up Mac Mail?
And when you set up the accounts, do you get a failure message when you set up the outgoing mail server? I mean, right at that point when you specify it in Mail Preferences?
Or does it appear to set up correctly, but when it's time to actually do email, it won't work?