What port number do you use when you set up those same SMTP credentials in your own email client (ie: Outlook, or Thunderbird, for example)?
Has your hosting company instructed you to use a particular port number? 25 is the normal outgoing email port. Sometimes other ports, such as 26, are enabled in case 25 is blocked for spam-prevention reasons (a common practice with home internet providers ... which is partly why I asked if you were hosting from home).