I used fdisk to partition the disk before installing the OS. Just to make sure all the partitions started on the physical sector boundaries. The fdisk output posted above looks fine, doesn't it? I followed this article
http://www.ibm.com/developerworks/linux/library/l-4kb-sector-disks/
Except for the sda4 all the other partitions start on sector that's a multiple of 8. I don't see any problem there.
could you please elaborate on your preference for parted over fdisk.
Is it GPT? If it's GPT, I cannot use it as my 5yr old laptop does not support it. Isn't EFI/UEFI needed to use GPT?