Ubuntu is currently using the 1.5.99.3 server, however there are a number of randr fixes in the git tree for the 1.6 branch subsequent to this version:
commit a82f10c5dd9fa74ff18759ab288bbd9c8b7ac4de
randr: clear primaryOutput when the output is deleted
commit 2bc53ce66828b6c177e3298fa2f326c77c93e136
randr: use primary output for RRFirstOutput()
commit f0234a9eb88ed103bca7db73a833c472ab95b48f
randr: Mangle GetScreenResources sort order based on primary output
commit 2ef02833d614c42693e019a444560e84f501b5dc
randr: Mangle compat Xinerama reply based on primary output
Ubuntu is currently using the 1.5.99.3 server, however there are a number of randr fixes in the git tree for the 1.6 branch subsequent to this version:
commit a82f10c5dd9fa74 ff18759ab288bbd 9c8b7ac4de
randr: clear primaryOutput when the output is deleted
commit 2bc53ce66828b6c 177e3298fa2f326 c77c93e136
randr: use primary output for RRFirstOutput()
commit f0234a9eb88ed10 3bca7db73a833c4 72ab95b48f
randr: Mangle GetScreenResources sort order based on primary output
commit 2ef02833d614c42 693e019a444560e 84f501b5dc
randr: Mangle compat Xinerama reply based on primary output
commit 0bdfdaa7df8105c 7ffc3248a4fdd5f 64da67103c
randr: Add [GS]etOutputPrimary
Looking at the diffs, none jump out at me as obvious fixes for this problem, but especially the first two sound to me like potentially relevant.