mail() not sending to Gmail, Yahoo etc.

[Canadian]

I'm using a simple form to grab an email address and send the person who signs up and automatic response.  It was working for a while and now it's not.  Not sure what happened.  My hosting company told me to look into my headers.  Can anyone help?  Here is my code.

 

Thanks,

 

<?php

			/* Set e-mail recipient */
			$subject = "Sign Up";
			$headers = "From: admin@xxx.com" . "\r\n" . "CC: admin@xxx.com";

			/* Check all form inputs using check_input function */
			$sign_up_email_address = check_input($_POST['sign_up_email_address'], "Please enter your email address.");

			/* If e-mail is not valid show error message */
			if (!preg_match("/([\w\-]+\@[\w\-]+\.[\w\-]+)/", $sign_up_email_address)) {

				show_error("E-mail address not valid");

			}

			/* Let's prepare the message for the e-mail */
			$response_message = "Sample Message";

			/* Send the message using mail() function */
			mail($sign_up_email_address, $subject, $response_message, $headers);

			/* Functions we used */
			function check_input($data, $problem='') {

				$data = trim($data);
				$data = stripslashes($data);
				$data = htmlspecialchars($data);

				if ($problem && strlen($data) == 0) {

					show_error($problem);
				}

				return $data;

			}

			function show_error($myError) {
			?>

			<?php echo $myError; ?>

 

Thank you,