Tienes que instalar un servidor de correo, ya sea POSTFIX o un equivalente, que se encargue de hacer el trabajo de envío de correo. PHP se limita a pasarle la información al servidor de correo.
No sé cómo se instala en ubuntu o kubuntu, pero en debian basta que pongas como root
y luego respondas algunas preguntas de configuración y tienes un MTA funcionando.
Saludos.