Actually, Frank is only partially correct. The problem is not that MiB alignment was chosen; that's actually the correct alignment. (Selecting cylinder alignment would definitely be wrong.) When using MiB alignment, partitions are aligned to 1MiB boundaries -- that is, they start on sectors whose numbers are multiples of 2048. Since 2048 is a multiple of 8, this means that all partitions begin on multiples of 8, which is required for optimum performance on Advanced Format disks. Most modern hard disks are Advanced Format models, so as a general rule you should use 1MiB (or at least 8-sector) alignment on modern disks. For further information on this, see this article I wrote on the subject for IBM developerWorks.

If you check the start sector numbers, you'll see that they all align on 2048-sector boundaries, except for one: /dev/sda2. It seems that fdisk is now providing a warning about this, with its Partition 2 does not start on physical sector boundary message. This message is a false alarm. Yes, it's true that it doesn't fit on an 8-sector boundary (30001150 / 8 = 3750143.75); but /dev/sda2 is also an exception to the rule I've just laid out. It's an extended partition, which means that it's a placeholder for logical partitions. The speed problems associated with misaligned partitions occur because filesystem data structures are read and written in 4KiB (8-sector) chunks; but the only data accessed directly through /dev/sda2 is the pointer to the first partition it contains, and that's a 512-byte data structure, so it occupies only part of a physical sector no matter what the extended partition's start point is. What's more, this data structure is read once when the computer boots and is rarely written. Thus, it doesn't matter what the alignment is on extended partitions, and any tool that complains about their misalignment is causing concern without reason.