I've boosted the contrast and crushed
Ironically, that's a recipe for muddiness. Matte papers have a certain range of tones they can represent, if try to force upon them a range of tones in excess of what they can handle, you get an ugly muddy mess.
Open up the shadows, and in particular increase the tonal range (I hesitate to say contrast) in the shadow areas. Separation is what you want in shadow areas for matte papers (and BTW glossy papers as well, but especially matte papers). In fact, separation is what you want everywhere.
Matte papers are about subtlety rather than punch. Could be you would prefer glossy.
Also be sure you've got all the color management stuff right. Classic mistake when going from glossy to matte is to forget to set the proper media type, in addition to the correct profile etc. etc. etc.
Don't know that particular printer and driver, but if it's swapping blacks inexplicably you might be bringing back in a wrong default media type (or even profile) when you reload a new file.