Here's a patch to libparted/labels/gpt.c that's a first stab at a solution. The changes:
1. Only the first partition may start at sector 1, don't modify later partitions that way. This avoids overlap.
2. If no protective partition at all is found, place at the start of the MBR a tiny fake protective partition, covering the space from sector 1 to the start of the first real partition. Partitions that follow are moved up by one, so that the hybrid MBR only includes three real partitions. (This approach is used by gpt-fdisk, see: http://www.rodsbooks.com/gdisk/hybrid.html )
This means if your GPT looks like this:
1. HFS: 1MB to 1GB
2. NTFS: 1GB to 2GB
3. ext3: 2GB to 3GB
4. ext4: 3GB to 4GB
The hybrid MBR will look like:
1. Protective: 512b to 1MB
2. HFS: 1MB to 1GB
3. NTFS: 1GB to 2GB
4. ext3: 2GB to 3GB
* Creation of a fake protective partition causes the partition numbering in the MBR to change. However, since parted currently produces partition tables that can't be read by Linux, this is almost certainly worth it.
* It might be best to create a fake initial protective partition in all cases where the first partition is not of type 0xEE. Thoughts?
* No attempt is made to leave certain partition types out of the hybrid MBR, for now (see issue #1 in my previous comment).