Tobin asks, "How the heck do I pull the 
connecting wires out of the block the relay plugs in to without 
destroying the wires and/or the plug receptacle?"

I'm not sure.  The female lug snaps into the plastic releay holder and the tab must be released somehow.  I'll let others comment on that.  BUT if that does not work there is always the option of snipping the wire you plan to replace about an inch or so from the relay holder, and neatly soldering a new wire to the inch piece.  Use heat shrink tuming for a neat job.  Of course, the relay block has tbe removed to do this.

--Nate