1. Do you have pins 18-25 on the parallel port grounded to the ground of your transistor?
2. Are you making sure that the port is addressed correctly i.e. 0x0378 for port 1?
3. What voltage are you using to energize the relay coil?
Take a look at my site in the signature and go to the projects section. There is an example there of a relay controlled H-bridge. Just use half of that design and it should work.