It's simply a case of not being able to generate the higher baud rate accurately enough with that crystal frequency. You need to get within a couple of percent or better. It's not that your PIC is sending gibberish, it's just sending at an inaccurate rate so the receiver sees gibberish.
Your crystal frequency gives an error of 17% at 115000 baud... no way that will work. Think, after six bits, the next bit is more than a full bit out of expected step.
Use a different crystal frequency.
Example: 14.7456MHz crystal, ((14745600/115200)/64)-1 = 1 exactly (perfect rate)
Note also that you can use a different frequency divisor (I think) on that PIC; check the data sheet. You can set it at 16, not 64, so your error will be a quarter.
That would make your ((16MHz/115000)/16)-1 = 7.7 so set to 8 is 4% error - that's still not good but might or might not work depending on what you connect to.
I would choose a better crystal for reliable 115000 baud.
Edit to add:
I think you can also do a /4 clock mode (set SFR bits BRGH and BRG16 to 1), so your case would become:
((16MHz/115000)/4)-1 = 33.72 so set to 34 is 0.8% error... that should work.