Relay Feedback Problem
simulate this circuit &ndash; Schematic created using CircuitLab

Figure 1. Using PNP doesn't always work well for level shifting.

If you have done as shown in Figure 1 you may find that the PNP transistor turns on without output from the micro. Q1's emitter-base junction will pass current through R1 and D1, the output protection diode, to the Vss of the micro. This may be enough to cause the relay to pick.
You should now see one of the advantages of NPN switching for (voltage) level-switching.

Your options are to go back to NPN, add an NPN 'inverter' in front of the PNP or use an opto-coupler to isolate the two circuits (where micro drives the LED and the transistor is installed in place of Q1). 
By the sound of things this isn't your only problem but it may be a start.