Since you must change the ticket over the phone, I honestly doubt that you're going to get anything different than what the phone reps quote. They're not the most thorough bunch in KUL, I know, but it is what it is. Sorry!

And yes, Q is the cheapest, so that's why they're probably quoting you up on the next level. The difference between Q and the next level is always a couple of hundred. You're right about the change fee, but the fare difference rule is always there.