Just curious - how are you driving the relay? I ask because parallel ports can't source or sink more than a couple milliamps at best. Higher currents can quickly cause damage.
Have you tested the parallel port's output with an LED + resistor or oscilloscope?