After each header, you usually add a "\r\n". It seems like the \n was giving us the problem so I took it off. So after each header I had instead "\r". It worked... so there you go.
For example:
$headers = 'From: someemail@email.com' . "\r";
$headers .= 'MIME-Version: 1.0' . "\r";
$headers .= 'Reply-To: replytoemail@email.com' . "\r";