Нет такой вещи, как "C # Web Service". Вы имеете в виду XML-веб-службу, основанную на удаленных вызовах SOAP и WSDL для описания.
Действительно, все службы SOAP должны быть взаимно совместимыми, будь то .Net, PHP или Java. Но на практике мелкие проблемы усложняют ситуацию.
Существует множество различных библиотек SOAP для PHP, но для подключения к веб-службе ASP.NET XML из PHP, но nuSOAP дал наилучшие результаты для меня. В основном это набор PHP-классов для использования веб-сервисов на основе SOAP. Простейший код клиента выглядит так:
<?php
// Pull in the NuSOAP code
require_once('nusoap.php');
// Create the client instance
$client = new soapclient('http://localhost/phphack/helloworld.php');
// Call the SOAP method
$result = $client->call('hello', array('name' => 'Scott'));
// Display the result
print_r($result);
?>
См. http://www.scottnichol.com/nusoapintro.htm для дополнительных примеров.