Yes, I have a 1N4004 connected to protect the transistor. I don't have the diode across the relay itself though, I have it on the PCB board.
I actually just read your example schematics, and it's exactly how my circuit is configured, which is why I'm scratching my head.
It works exactly as expected (switches completely on and off) if I use my voltmeter to test with the on-board voltage regulator's 5v power output, the same power that powers the PIC. It goes from +5.00v to 0.00v, measured from the +5v at the voltage regulator to the collector of the transistor. But when I try using the +14v supply that supplies the board, voltage regulator, relay coil, etc, everything gets all funky. Without the coil it goes from about +14v to +6v, with the coil it goes from 9.31v to 9.20v.