finalmente con el setlocale que han puesto Eleazan y abimaelrc si sale en español, el problema es que si pongo %d si sale el día con un cero delante si es un sólo digito, pero si pongo %e, que es lo que he leído en la página de php, no sale nada.
Código PHP:
// No sale el día
$fecha = strftime('%A %e %B %Y',$datos["fecha"]);
//sale el día con un cero delante si es menor que 10
$fecha = strftime('%A %d %B %Y',$datos["fecha"]);