CAN bus and UART interfering
The PIC 18F4680 is capable of running its UART and CAN module at the same time.  If these are working separately, but not together when both are being used heavily, something is probably getting overrun.

Your firmware architecture matters a lot here.  You probably have a congested interrupt routine.  I have done CAN and UART I/O together on several PICs, including some in the 18F series.  I use a minimal cooperative multi-tasking system for such things.  It greatly simplifies the firmware architecture to dedicate a task to receiving from each communications port.  In the UART case, the interrupt routine stuffs received bytes into a FIFO, which the UART-reading task then drains as it gets around to it.  For CAN, I don't use interrupts at all, just have the CAN receiving task poll for the next CAN frame being available, process it, then go back and do it again.  Note that polling on a event in the multi-tasking system is a loop that includes a call to TASK_YIELD each iteration.  That allows other tasks to use the processor.

The obvious first thing to do is to verify that you are running the PIC at its max clock rate.  After that, don't do silly things in the firmware.  This is a case where a well thought out firmware architecture really matters.  Particularly examine your interrupt strategy.  Do as little as possible in the interrupt to reduce hardware service latency, then handle most things in foreground code.  Writing the interrupt routine in assembler may be a good idea.  I've seen compilers add a lot of bloat to interrupt routines.

If you still can't get your 20 pounds of code down to reasonable 10 pound size, then get a 30 pound PIC.  There are 33EP series, for example, that also have both UART and CAN modules.  The faster instruction execution rate allows for more sloppiness before the system breaks.  However, again, good code architecture is the real solution.