PIC24FJ Baud Rate Issues / Crystal Selection
The answer is that I should be using the BRGH flag which provides 4 BRG cycles per bit, rather than 16.

This makes the BRG calculation:

BRG = ((16000000/115200)/4) - 1 (33.72, or 34)


The effective baud rate at this BRG is 114286 or 0.8% error rate, which is perfectly acceptable.