What do you mean by "The tones will play, but the on-hold message won't"?

When you place a call on hold, do you hear tones (beeping every 10 seconds or so) or dead air? If it's tones, you have to change the setting in programming.

Easy way to test too is to turn on the background music in system programming and then use Feature 86 on a set. If the audio is making it to the system, it will play on the speaker of the phone.