MSB=000 and LSB=000 is an OK start

http://download.yamaha.com/api/asset/file/?language=en&site=uk.yamaha.com&asset_id=67294

Page 174 - notice the "Program No." column 0-127 (or 1-128 if your method of entry is 1-based).

Are you sending the PC (program change) byte along with MSB/LSB? This corresponds to the "Program No.".

Also, I believe GM does not have a multi-part setting, meaning it will change all PARTs at one time. It appears to only target a single PART like the single-part (in the chart) do. So whichever MIDI channel you are sending the MSB/LSB+PC on - this will change the target PART to the new GM value.

All values below are in hex:

B0 00 00 - MSB=0 (MIDI Channel 1)
B0 20 00 - LSB=0 (MIDI Channel 1)
C0 00 - PC=0 (MIDI Channel 1)

This changes PART 1 to "Concert GrandPiano"

B0 00 00 - MSB=0 (MIDI Channel 1)
B0 20 00 - LSB=0 (MIDI Channel 1)
C0 55 - PC=55 (MIDI Channel 1)

This changes PART 1 to "Voice Lead"

B1 00 00 - MSB=0 (MIDI Channel 2)
B1 20 00 - LSB=0 (MIDI Channel 2)
C1 00 - PC=0 (MIDI Channel 2)

This changes PART 2 to "Concert GrandPiano"

Notice same as 1st example - but B0 and C0 are changed to B1 and C1 - since lower nibble (the 0 vs 1) is the target MIDI channel and is 0-based (0=MIDI channel 1, 1=MIDI channel 2) ... and PART = MIDI Channel.

Hi Jason, yes, I send PC along with MSB/LSB but that doesn't work on the montage. It doesn't go to the GM sounds. When the midimassage is done I see that the sound has changed but not to the sound I want.

For instance drums, I send the message on part 10 (midichannel 10)
MSB=127
LSB=0
PC=0

Part 10 was set to a "normal" not-GM sound, after the midimessage is doesn't go to the GM-drums but to a pianosound....

It has no choice but to change. If you are getting a piano sound that indicates the PC (Program Change) was received but the Bank Select message was missed. There are a few things to check.

Bank Select messages can be filtered by Montage independent of the Program Change message, you would have to have changed this setting from the default.
[UTILITY] > "Settings" > "Advanced"

If both are On, then verify that you have entered the Bank Select message correctly in the sending device.

For me, I cannot send GM changes to an empty PART. So I tried sending (keeping with my previous all values in hex) MSB=7F, LSB=00, PC=00 to PART 10 (B9 and C9 MIDI op codes = MIDI channel 10) and nothing happened when I had PART 10 = empty. I then placed a random random part in PART (slot) 10 and sent the same message. This time - I see the PART name now changed to "Stereo GM Kit" and is properly working as a drum kit.

Perhaps this is what you're seeing on your end?

If you start with Multi/GM as the initialized performance - then all 16 PARTs will be non-empty allowing to accept the MSB/LSB+PC for each.

Just focusing right now on the program changes and not on things like local keyboard control.

If using the Montage as a multi-timbral Tone Engine with a MIDI FILE, it is recommended that you start with the [CATEGORY SEARCH] > "Init" > "Multi/GM" template as your starting point... this places a program in each PART slot and allows you to use BANK SELECT and PROGRAM CHANGE messages to switch programs.