Try:
mail('your@email.com', 'Subject', 'Message', "FROM: Me <from@email.com>\r\n");
From the manual:
Note: When sending mail, the mail must contain a From header. This can be set with the additional_headers parameter, or a default can be set in php.ini.