Can a Windows Server 2008 use a GPT-only partition table

Not too tricky. Hopefully.

First of all, note the size and order of all your partitions on /dev/sda:

challenger:/home/michael # grep . /sys/block/sda/sda*/{start,size}
/sys/block/sda/sda1/start:63
/sys/block/sda/sda2/start:228690000
/sys/block/sda/sda3/start:257040
/sys/block/sda/sda1/size:256977
/sys/block/sda/sda2/size:83885760
/sys/block/sda/sda3/size:228432960

Run fdisk on /dev/sda and change the units to sectors:

Command (m for help): u
Changing display/entry units to sectors

Then start making partitions. Use the appropriate numbers start and size for each partition.
Avoid an off-by-one error - subtract one from size before typing it into fdisk.

Command (m for help): n
Command action
   e   extended
   p   primary partition (1-4)
p
Partition number (1-4): 1
First sector (63-312581807, default 63): 
Using default value 63
Last sector, +sectors or +size{K,M,G} (63-312581807, default 312581807): +256976

Command (m for help): p

Disk /dev/sda: 160.0 GB, 160041885696 bytes
255 heads, 63 sectors/track, 19457 cylinders, total 312581808 sectors
Units = sectors of 1 * 512 = 512 bytes
Disk identifier: 0x02b002af

   Device Boot      Start         End      Blocks   Id  System
/dev/sda1              63      257039      128488+  83  Linux

Don't forget to set your partition IDs and toggle the boot flag on the right partition

Now re-install your MBR and you should be ready to go.

Naturally you can do all this using your favorite partition editor... parted works just fine as well.

If you've lost the information regarding start/end of partitions - parted has 'rescue' options to search the disk for lost partitions. But you shouldn't need those.

Solution is to use a bios_grub partition, which is not the same as the /boot partition.

By default the bios_grub partition is 1MiB, and it must be flagged bios_grub. Mine is the first partition on my disk. If your partition 2 is actually /boot as parted suggests, that would not be correct and you should make another 1MiB partition.

With GPT and GRUB2 the minimum filesystem has three partitions: bios_grub, root, swap. (not perfectly sure swap is required)

Why does grub fail to boot after simply running "grub-install"?

Unknown... You'd think it wouldn't modify anything if it says clearly it cannot embed so it can't work.

Why does it say "file not found"?

/vmlinuz is a symlink that uses the boot partition, and the boot partition is corrupt. The bios_grub code was written on top of its ext3 structure. This probably meant that /boot was not mounted, and the grub files seen there were actually on the root system, which didn't contain the kernel.

Why doesn't grub want to install without this setting I set with parted

A GPT partition table has no space for a bootloader, unlike MBR. So a specific partition must be created to hold the boot code. Before running "grub-install", specify this partition with the command:

    parted /dev/sda set 1 bios_grub on

I thought all I needed was a separate /boot. How does the Ubuntu CD installer install it without the bios_grub setting?

This requirement seems to be all that is needed for the Ubuntu installer, but it creates an unstandard system which is broken easily.

When GRUB says "This GPT partition label has no BIOS Boot Partition", it means the bios_grub partition, not /boot.