Separiamo i problemi
Il servizio WCF si avvia tramite WcfSvcHost.exe?
Se sì riesci a contattarlo con WCFTestClient.exe?

entrambi sono tra gli strumenti di VS e li trovi in
"C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\IDE" ( se hai vs 2008, o nell'analoga cartella )

In ogni caso se metti il progetto WCF come Start Up Project VS dovrebbe avviarteli entrambi se lanci il Debug ( F5 )

questo per escludere che il problema sia nel servizio.