cfdisk and fdisk are both part of (upstream) util-linux-ng[*1], so both handle large sectors the same. In Squeeze they are both (currently) at 2.17.2-9.
I used gparted-live-0.8.1-3 (debian based with 2.6.38 kernel) to partition it, I believe util-linux version on this image is 2.19. Then I used the Debian installer to set-up LUKS and LVM.
Looks like a hardware problem - I'd try another cable.
I don't think it's a connector issue. It's laptop but it uses a SATA 1.5Gbps controller. Old drive works fine.
I sent WD the error messages from Western Digital Data LifeGuard Diagnostics Extended test output. Wait and see what they have to say.
I really don't think it's a linux specific issue. Running this software from the Windows partition, I guess it really does not matter what's on the other partitions.