This is on a Nexus 4 running Kitkat. Latest version of Calibre Sync (1.1.4.1) and Calibre 1.26. The desktop is running Debian testing.
Editing my post because I figured out at least part of my original problem; I had a mismatch between the defined Root directory and where books are actually stored on my phone. At this point I think the problem is in the way that Calibre Sync defines directories and it is not a Calibre problem after all.