As with teaching a horse anything, you may have to over exaggerate in the beginning. Make your aids as big as possible. And then reward any small improvement. After that, it's just repetition. As your horses gets more clued in to what it is you're asking, your aids can get smaller and more refined.
It helps to have a visual marker, such as going over a pole on the ground where the lead change is going to happen. The nice thing about the pole is that it encourages the legs to lift anyway, which is half the effort of changing the lead. Have it in the diagonal of the arena first, just so you have time to prepare and time to settle if it goes wrong. Having it too close to the corner in the beginning may throw your horse off as it also needs to think about its balance around the corner. As it gets more used to it, the pole can be moved closer.
Always finish on a good note. No matter what you're training your horse to do, anyways finish with a positive.