Note that some WD Advanced Format drives currently available on the market have 4096 byte physical sectors, but hide that fact from the outside world and only report 512 byte sectors.
See this discussion on util-linux-ng mailing list:
The only reasonable solution for this is to align partitions by default on a boundary that's known to be almost always good, unless the exact drive topology can be determined.
The consensus regarding util-linux's fdisk (and the already committed fix) is to align on a 1MiB boundary by default:
It's unclear whether parted-2.1 does this already or does it need an analogous fix like fdisk did: