> I'm not sure "it can be generalized to an undecidable problem" really explains why it's hard....

Hah! I agree with this. :)