oltre al giorno dovresti fare anche l'array del mese. Ti metto un esempio con solo il giorno. Tu fai il resto ed estendilo anche con il mese.
codice:
Function PrimaDataInLettere($Giorno, $Mese, $Anno)
 {
   $TimeStamp = mktime(0,0,0, $Mese, $Giorno, $Anno);
   $PrimaData = date("d F Y", $TimeStamp);
   $day =  date('w', mktime(0,0,0, $Mese, $Giorno, $Anno));
   $giorno_sett = array ("Domenica", "Lunedi", "Martedi", "Mercoledi",
                         "Giovedi", "Venerdi", "Sabato");
   $giorno = $giorno_sett[$day];
   $PrimaDataIta = $giorno ." ". $PrimaData;
   return $PrimaDataIta;
 }

  print (" 


       <font face='Verdana' size='2'>Prima data inserita:
       " .PrimaDataInLettere(28, 10, 2005). " 
       </font></p>
        ");
Attenzione all'ordine dei valori in mktime... sono all'inglese: mese, giorno, anno