I had issues with serial comms when moving code from an 16F877A to an 18F4580. Turns out it was due to the crystal. I had been using a 20Mhz with an OSC 48 defined - when used with the 18F the program would still run but serial comms at 115200 was garbage - following advice from forum members I changed the xtal to 12Mhz and ran with the HS_PLL defined and same OSC defined and that worked for me.

As Bruce stated, post up your complete code or at least the defines and what Xtal you are using