ORIGINAL: Gtarling
It's possible that a newer programmer won't recognize an older servo. If the programmer worked OK with your new(?) elevator servos, then I think this is the most likely answer. If you know anyone with an older programmer, it may be worth a try with that.
Two reasons why I don't think this is the issue:
1. It worked the first time
2. The HS-5625MG is listed as compatible with the programmer
Thanks for the suggestion, though!