If the PIC send without any poblem to a PC then its OK for the 4MHz.

I have many times used 9600 on 628 with 4MHz resonator (not crystal) and went smooth.

Ioannis