Count and LongCount are not supported in Silverligth because they require a synchornous execution of the query. Since Silverlight requires all network operations to by asynchronous this is not possible.
You can either issue the HTTP query in question programatically not using DataServiceContext (or related classes), since the $count returns a text representation of the number, parsing the response is not that hard.
Or you can use a bit of a trick. You can use IncludeTotalCount() to add $inlinecount=allpages query option to the query which will include the count in the response. Then to not download all the entities from server, you can use Take(0) which will add $top=0 and thus return empty result set. But the inline count will still contain the right number.
You can access the inline count on the QueryOperationResponse.TotalCount property.
Something like this:
NetflixCatalog ctx = new NetflixCatalog(new Uri("http://netflix.cloudapp.net/Catalog"));
var q = (DataServiceQuery<Genre>)ctx.Genres.IncludeTotalCount().Take(0);
q.BeginExecute((ar) =>
{
QueryOperationResponse<Genre> r = (QueryOperationResponse<Genre>)q.EndExecute(ar);
r.TotalCount.ToString(); // Use the count in whatever way you need
}, null);