Mailgun (SMTP) + Craft
Craft is just passing on the error message it gets back when trying to connect with whatever settings it was given.

And we're using Mailgun ourselves (port 587) for sending emails on https://craftcms.com, which is a Craft install.

Make sure you're using smtp.mailgun.org as the host and that you've got the transport type set to TLS as well.