Try calling GetContent first with
string result = mysiteDataServiceInstance.GetContent(SiteDataService.ObjectType.ContentDatabase,
myContentDbGuid.ToString(), "", "", false, false, ref lastChangeID);
Where lastChangeID is an empty string. This should give back results like
<ContentDatabase><Metadata ChangeId="1;0;146b129e-4f56-4701-ada2-b370744f2ca3;633896405160170000;168811216" ID="{146b129e-4f56-4701-ada2-b370744f2ca3}" /></ContentDatabase>
Where 146b129e-4f56-4701-ada2-b370744f2ca3 is the guid of my ContentDb
The ChangeId mentioned here can be used in place of the lastChangeId and currentChangeId.
My results appeared like
<SPContentDatabase Change="Unchanged" ItemCount="0">
<ContentDatabase><Metadata ChangeId="1;0;146b129e-4f56-4701-ada2-b370744f2ca3;633896953296070000;30349699" ID="{146b129e-4f56-4701-ada2-b370744f2ca3}" /></ContentDatabase></SPContentDatabase>
The process is exactly the same when using SiteDataService.ObjectType.Site