in theory using the internal USART and 4MHZ will work really well @4MHZ. Even higher baudrate is possible using the calc. Example 19200 bauds with BRGH=1 give a 0.16% error... really great. Can probably work with DEBUG too.

BUT with the internal OSC, that might cause problem.

In this case as it's seems to work with a 16F628 but not with 16F628A, i suspect a device programmer problem or device programmer software problem. Sure the 0.1uF cap is not sit close to the PIC.

How about if you sit one on of those cap on the ZIFF socket while programming?