For best compatibility you schould only use intrinsic types like int, string or double in the interface definition. User defined complex types must be attibuted as "Data contract" and schould contain only intrinsic types to get 100% Web Service compatibility.
Christoph is right in the compatibility front. And again, remembering the whole point of this exercise is to be able to have non-Windows (or at least non .Net-enabled) devices as clients we can't rely on .Net complex types.
My WS version abstracts all this and serialises all the complex results into standardised XML structures which can be bound to schemas so that any potential clients can basically receive the WS response and then parse the resulting XML construct easily.
Things like GetChannelList(), AddSchedule() and DeleteRecording() become then a very simple WS interface with which to work.
Also, gljubojevic's suggestion of an TVServer client interface is most definitely the way to go as far as the server is concerned, although from the point of view of the client this is transparent, as the WS client will not deal in interfaces but in contracts using UDDI, WSDL and other associated technologies...
AL