I second Pangkor Island - not Pangkor Laut - absolutely secluded, white beaches, gorgeous...
Went in 2001 during the WTC attacks, didn't hear anything about it until we got back!!!
Pangkor Laut is supposed to be lush too... Pavorotti said he wept when he saw the place!!!
Ewwwww, the sight of a 20 stone opera singer bawling his eyes out!!!!