The interesting bit about Malaysia is that the country has very distinct areas for muslims and non-muslims. The funny thing is in the cities, muslims are usually pretty open minded. A lot of muslim women don't usually wear veil (or tudong, in Malay), except special occasions like Ramadan and Puasa.
Tudong is the Malay version of the headscarf.
Malaysia's fine to visit...just don't go visiting the northern states (Kelantan, Terengganu), which is where most of the more crazy muslim stuff happens.
Small correction, Terengganu and Kelantan are in the western region of the peninsular. The northen region of the peninsular consists of Penang, Kedah, Perak, Kelantan and part of Pahang. You're right about not visiting those two states though, not if you're a huge sea turtle fan or researcher

The majority of the fundamental muslims live in those two States. Otherwise, it's still a pretty country to visit
