Azure Table Storage - One of the request inputs is not valid

I was getting this error while getting the count of the total number of entities for a given Partition Key in a Azure Storage Table:

System.Data.Services.Client.DataServiceQueryException: An error occurred while processing this request. ---> System.Data.Services.Client.DataServiceClientException: <?xml version="1.0" encoding="utf-8" standalone="yes"?>
<error xmlns="http://schemas.microsoft.com/ado/2007/08/dataservices/metadata">
  <code>InvalidInput</code>
  <message xml:lang="en-US">One of the request inputs is not valid.RequestId:xxxTime:xxx</message>
</error>

This was occuring when I was trying to get the count like this:
int count = (from e in tableContext.CreateQuery<MyEntity>(_myTable)
                     where e.PartitionKey == interalId
                     select e).Count();

I was hoping for it to work since I was able to get the entire List using the same approach:
(from e in tableContext.CreateQuery<MyEntity>(_myTable)
                     where e.PartitionKey == interalId
                     select e).ToList();

However, I didn't want to first get the entire List and then take the count which would be lot of size overhead over the network. Finally I was able to get the count by first creating a query and then calling Execute:
CloudTableQuery<MyEntity> query = (from e in tableContext.CreateQuery<MyEntity>(_myTable)
                     where e.PartitionKey == interalId
                     select e).AsTableServiceQuery();
int count = query.Execute().Count();