It could be that your host is blocking the port or blocking the use of external SMTP servers (some hosts do this as a (rather inneffective) form of spam prevention). Since the incoming server configuration worked correctly, that sounds like a good possibility. I'd advise contacting your host and asking them about it.
We had a minor issue getting started with Google Apps SMTP, we found the 465 port didn't work and ended up using 587.
Some hosts do block these ports, a couple of hosts I know don't include:
(puppetHosting) (shared hosting & VPS - you need to contact them for info re VPS as they are currently updating their offering)
(MDD Hosting) (shared hosting - never tried their VPS)
(Linode) (VPS hosting only)
We currently have accounts with all of these providers, they all are very reliable and I would (currently) recommend them all.
Remember with any VPS you generally get SSH access and you may not get a control panel (such as cPanel, Plesk or Hesk) without paying extra for it.