4 days in Pinang is bit too much (there isn't that much to see) and Melaka can also be shortened to one day (do it as an overnight trip from KL).

But aren't you interested in nature and wildlife?

Flying to Kota Bharu or Kuala Terengganu is ok. Or if you prefer you could travel to the Cameron Highlands by bus, stop for one day, then continue the next day by bus to the east coast.

Another option is to travel to Taman Negara, stop a couple of days there, then continue overland to the east coast.

To get to Perhentian you need to catch the boat in Kuala Besut (to get there take a taxi in Kota Bharu). To get to Redang, either fly from KL (Subang airport) with Berjaya or fly KL-Kuala Terengganu, then take a taxi to Merang and then the boat to Redang.

There should be a bus connecting Pinang with Kota Bharu.

Small addition: firefly has flights from Pinang to Kota Bharu:
http://www.fireflyz.com.my/

We spent a week in Georgetown, Penang and just loved it.

amin must be from the area to not find it interesting...

thanks very much for the suggestions.

I will consider both Cameron Highlands and Tama Negara, cutting 1 day from Melaka.

CH is on the way from KL to Penang so we would need surface transports rather than flying, which is also good. Itinerary would be KL-CH-Penang.

In our clockwise roundtrip Taman Negara would be on the return way between the East Coast and KL, then my major concern is how to cross from West/Penang to East Coast. Any idea of bus comopanies doing this route from Penang to Kota Bharu?

We will do boat trips to one the the Islands. My wife hates small aircrafts.

we also loved georgetown and spent 4 days there..

one full day in K/L is worthwhile..

Actually I live in Germany, but I can't imagine how somebody would spend an entire week in Pinang. Already 4 days are too much, but see here how Pinang looks like:
http://www.molon.de/galleries/Malaysia/WestCoast/Pinang/

In any case, try the following schedule:

Day 1: arrive in KL
Day 2: KL -> CH by bus; visit the tea plantations and other sights in the afternoon
Day 3: CH -> Pinang: some trekking in the CH, evening bus to Pinang (Georgetown)
Day 4 + Day 5: Pinang
Day 6: 7am flight to Kota Bharu, arrival 7:55, taxi to Kuala Besut, boat to Perhentian; day in Perhentian
Day 7-10: Perhentian
Day 11: overland transfer (boat + bus or train) to Taman Negara; arrive in the afternoon
Day 12-13: Taman Negara, trekking etc.
Day 14: Taman Negara -> Melaka (boat to Kuala Tembeling, taxi to Jerantut, jungle train from Jerantut to Gemas, taxi from Gemas to Melaka; going through KL will take longer and won't be as scenic): arrive in Melaka in the afternoon
Day 15: morning in Melaka, afternoon bus to KL

As you can see the schedule is a bit tight, so you might consider dropping for instance the Cameron highlands and flying straight away from KL to Pinang which would save you two days (although actually the CH are interesting especially for the tea plantations, see http://www.molon.de/galleries/Malaysia/WestCoast/Cameron/ ). In any case there is no time for 4 days in Pinang.

We all travel differently, amin. As I said, we spent a week in Georgetown, visiting temples and historic sites, wandering though the ethnic neighborhoods and enjoying what is perhaps the best hawker food in SE Asia. We had a wonderful time and would return.

Your itinerary wouldn't work for me, I expect any itinerary I proposed wouldn't work for you. You have a lot of trekking in your schedule, which is not what many people would be looking for.

Trekking can mean a comfortable walk in the forest, easily doable by anybody, doesn't have to be a Mt Kilimanjaro climb. But let the poster decide what he wants to do and see. Good hawker food is available virtually anywhere in Malaysia.

wow ! I am lerning a lot from both of you !

amln: thanks for your detailled itinerary. I have to check better into details Cameron Highlands and Taman Negara, then talk to the rest of the family, maybe we could take one of those two. So you would pick Perhentian vs. Redang ?

Kathie: I understand your point regarding Pinang. I have to find the right balance and negotiate with wife and daughter all alternatives

Now I have enough stuff for my homework this weekend !

thanks again

Here are some photos of Redang and Perhentian:
http://www.molon.de/galleries/Malaysia/EastCoast/Redang/
http://www.molon.de/galleries/Malaysia/EastCoast/Perhentian/

Both islands are beautiful.

Redang is more upmarket, more expensive accomodation, organised into resorts, lots of Malaysian and Singaporean tourists visiting on a package.
Perhentian is more unstructured, backpacker level, is more wild, in my opinion more a little bit more beautiful.

almn how much would cost a taxi from KLIA to Melaka ? Our flight arrives at 5pm and would like to go straight to Melaka to avoid a useless night in KL and the next morning bus to Melaka. We are going to spend 2 nights in KL at the end of the trip.

Just guessing from the distance (136km): should be less than RM200, perhaps less than RM 150.