Mas777 is absolutely correct regarding MAS' flights out from Europe into Kuala Lumpur. You could check that MH 1/3/5/7/9/11/17/21 are fully booked. If MAS is getting so booked up in their European sector, I don't see why BA can't make use of their Heathrow hub and connect these passengers to Kuala Lumpur, thus generating more ex-European passengers. Also, to a smaller extent, connect passengers across the Atlantic where they previously used to do so, onwards to Kuala Lumpur.
Currently, MAS is the sole carrier providing nonstop services between Kuala Lumpur and London, providing about 355,000 seats a year. In 2001, there were about 262,000 British tourist visiting Malaysia, plus about another 180,000 or so tourist from other European countries (exlcuding Scandinavia, which makes up another 82,000 tourist) with easy access to London-Heathrow airport and that sums to about 442,000 tourist arrivals. One could do the math and see very well that MAS can't even cope with the European tourist traffic alone and we are not even considering passengers traveling for business purposes, the Malaysian tourist to Europe, which normally use London as their gateway and not to mention the huge Malaysian student population in the UK.
Also, there are a lot of British companies that are investing in Malaysia and vice versa and the reason for lack of premium traffic is perhaps invalid in this case. British expatriates residing in Malaysia would perhaps love to fly with BA to London since it's their national carrier, but they are offered Virgin instead, only to discover that it's on a code-share basis with MAS and the beauty of this nonstop service with MAS instead of transiting and changing terminals in Singapore.
When they started to code-share with Cathay Pacific on the latter's HKG-KUL route, BA offered a "cheap" alternative to Kuala Lumpur, prices in the Economy starting at £800, where I could probably fly Business with Qatar Airways, Emirates or Sri Lankan. Which sane person would want to pay £800 just to fly with BA and then transit in Hong Kong for another 4 hours flight to Kuala Lumpur.
Have you ever traveled on flights between London and Kuala Lumpur? Do you know how hard it is to get a seat to Kuala Lumpur? I had booked my flights to Kuala Lumpur for the Christmas season and I was unable to fly with MAS because their flights are full to the brim. Thus, I need to resort to fly with SIA instead.
By the way, it's not only "Muslim-states" states carriers that are increasing their capacity into Kuala Lumpur. China Southern, Korean Airlines, JAL had increased their capacity into KUL and recently Air Macau inaugrated services into KUL.