Your math seems good. I'm wondering if the 'holding' current is not much lower than the 'turn on' current. Any specs on that?
edit: OK, so I looked at the data sheet. all the current, resistance, etc., looks pretty much in line with 22mA and 9v for all conditions. The data sheet says it will take 200% of rated voltage (indefinitely?). so downsize your resistor until it pulls in. Or use a regulator to get your control voltage. I'm still thinking the 1k resistor is 'choking' the relay.