UART on dsPIC33EP512MU810
This is most likely a baud rate/clock error.  Try capturing the TX line on a scope and measure the baud rate you actually see, compared to what you've programmed.  From that you should be able to tell that you're off by a specific ratio, and with any luck that will make it easier to track down the bug.

Since you've tried various baud rates and none look right, you may be unintentionally creating a "non-standard" baud rate.  You're using FP = 40000000 (40MHz). Can you confirm the chip is running at 40MHz? I don't see your PLL settings, so I can't say for sure.