I tried the following method and it worked:
- Boot installation CD (or usb stick) so you get the page showing HD needs, internet connection etc.
- Press Ctrl+alt+F1 to get into "terminal mode".
- Run sudo parted -a optimal /dev/sda (change drive name accordingly). This will startup parted with this optimal setting for this drive.