You should NOT need to open any special ports to be able to send mail using SMTP -- you should be able to do it with a stock (fully closed) software firewall and a stock (fully closed) hardware firewall. Opening ports is actually for when the traffic initiates from the outside on that port. The SMTP traffic is initiating from the inside so having the port open is irrelevant.
What was your configuration before you had the router? Were you plugged directly into a cable modem or DSL modem? Can you please describe in more detail exactly what you changed?
Usually, this issue has to do with an ISP (Cable or DSL) putting in restrictions so that mail can only be sent on *their* smtp servers. For instance, using my same set of mail accounts (Yahoo, Hotmail, GMail, NetZero, 2x University of Florida, AOL), I can send all of them across SMTP. However, when I am at home, I must use the Cox Cable SMTP server. When I am at the University, I must use the university's server. Neither site lets me send SMTP using any server other than their own.