Connection refused. Why can't I send email from one server but I can from another?

Solved! It turned out that the hosting provider had some trial account blocks in place to stop abuse. Apparently these would normally be lifted once new customers go through authentication (which I've done) but they weren't. Thankfully they have now been and I can send email perfectly.

So the lesson here: don't assume anything! Go back to your provider first to check with them if anything could be hindering what you're up to.

Sorry to have troubled you fine people. Thank you for all of your suggestions. They all helped find the answer in the end :)