To change the port of your outgoing server, see the bottom screenshot on this page:

Outlook 2007 Screenshots

“Outlook Email Options”

You can get there by going to Tools -> Account Settings. Then select Advanced and then change 25 to 587.

UPDATE: Seems like every ISP (including Verizon FIOS) is now closing port 25!