In the past I had problems changing dates over the phone - my suspicion is that the first agent I spoke to tried to search for both legs on the same day, which triggered an error because this would put the SIN-MEL leg starting before the LHR-SIN flight took off. I could see availability on the website so I knew the agent wasn't doing it right. HUCA and I spoke to someone who could do it.