SMTP and hosting company

Hello y'all!

Basically I took up Randy Hoyt's advice and tried to use an external email server to handle the contact form on my website. I used PHPmailer as well. The way I set up the connection to this mailserver is as followed:

require_once("inc/packages/class.phpmailer.php");
            $mail = new PHPMailer();

            $mail->IsSMTP();               
            $mail->SMTPAuth = true;             
            $mail->SMTPSecure = "tls";                 
            $mail->Host = "smtp.gmail.com";     
            $mail->Port = 587;                 
            $mail->Username = "correctmail@gmail.com"; 
            $mail->Password = "totallysecure";

As you can see, I tried to use the gmail mail server (is that what I did? I'm new to this). Now, this totally worked on localhost, after changing some things in php.ini. I filled in my contact form, clicked send, and the mail arrived in my gmail inbox. Nice!

But then I uploaded it to my webhost, one.com. When I tried the form there, sending the form caused an error, saying it could not connect to the server.

When I contacted them, all they said was "You should use our smtp". Naturally, being a true internet freedomfighter, these words caused me to throw a tantrum.

What do you guys suggest I do?