Hola a todos.
El trozo de código a continuación soluciona mi problema solo resta que me digan si hay una manera mejor.-

string dia = datetime.ToString("dddd");
dia = char.ToUpper(dia[0]) + dia.Substring(1);
string mes = datetime.ToString("MMMM");
mes = char.ToUpper(mes[0]) + mes.Substring(1);
Console.Write(" \n Ingresó...: " + " " + dia + " " + datetime.Day + " de " + mes
		+ " de " + datetime.Year);

Saludos.
Daniel

Sí, se puede mejorar mucho.

1 - Puedes evitar la declaración de todas las variables (Ya que solo le das uso una única vez, para eso es mejor "usar" diréctamente en 1 paso, en lugar de los 3 pasos que dás: "declarar variable + almacenar contenido en variable + usar variable").
2 - En lugar de una comparación me parece más correcto añadir un control de errores (Un Try/Catch por si en un futuro quieres añadir aún más tipos de excepciones, en lugar de añadir más If's).
3 - Para la organización de los elementos del string debes usar "String.Format": http://msdn.microsoft.com/en-us/library/system.string.format.aspx
4 - Para el formato de la fecha es tán simple como usar el método "ToString" con el formato adecuado ("D"): http://msdn.microsoft.com/en-us/library/zdtaw1bw.aspx .
5 - Para el formato del string resultante, puedes usar la función "ToTitleCase", y hacer un pequeñísimo ajuste añadiendo un "Replace" para modificar "De" por "de".
En fin... en general se puede simplificar bastante el code.

Aquí tienes, en VB:

Imports System.Globalization
 
Module Module1
 
    Sub Main(args As String())
        ValidarFecha()
        Console.ReadLine()
    End Sub
 
    Private Sub ValidarFecha()
 
        Console.Write("Ingrese una fecha(ej. 07-07-2013)....:")
 
        Try
 
            Console.WriteLine(CultureInfo.CurrentCulture.TextInfo.ToTitleCase( _
                              String.Format("Ingresó: {0}", _
                              Date.Parse(Console.ReadLine).ToString("D"))).Replace("De", "de"))
 
        Catch ' ex As Exception
            Console.WriteLine("No es una fecha valida...")
        End Try
 
    End Sub
 
End Module

En C#:
(Este me ha costado un poquito, he tenido que usar convertidor online, hacer algunas correcciones manuales, y ajustar las indentaciones innecesarias)

    using System;
    using System.Globalization;
 
    static class Module1 {
 
       public static void Main(string[] args) {
           ValidarFecha();
           Console.ReadLine();
       }
 
       private static void ValidarFecha() {
 
           Console.WriteLine("Ingrese una fecha (ej. 07-07-2013)...:");
 
           try {
 
               Console.WriteLine(CultureInfo.CurrentCulture.TextInfo.ToTitleCase(
                                 string.Format("Ingresó: {0}",
                                 DateTime.Parse(Console.ReadLine()).ToString("D"))).Replace("De", "de"));
 
           } catch {
 
               Console.WriteLine("No es una fecha valida...");
 
           } // Try
 
       } // ValidarFecha
 
    } // Module1

Saludos!