For a switching type application you want the transistor to be fully saturated. If you're not worried about power consumption, which I guess you're not since you're using a relay, just run 15-20mA thru the LED and measure the voltage across collector/emitter, in saturation it should be around 1V or less. If it is you can decrease the LED current, if it isn't you need to increase it.

/Henrik.