Based on the blog post by Windows Azure Storage team - How to get most out of Windows Azure Tables
(scroll down to Queries
section in the post, point #4), queries involving OR
are not optimized and would result in full table scan. You may be running into issues because of that.
You may want to change your query to avoid this situation. A few things you could try are:
((PartitionKey ge '2013100606') and (PartitionKey le '2013100607')) and (cid eq '18831')
(PartitionKey eq '2013100606' and cid eq '18831') or (PartitionKey eq '2013100607' and cid eq '18831')
See if doing any of these help. Instead of 2nd query, you could fire two separate queries in parallel.