Many physicists believed that quantum entanglement would (eventually) be understood in terms of some simple-to-compute measure. The surprising mathematical finding that the quantum separability problem is NP-hard proved these expectations to be wrong.
See, for example, Lawrence M. Ioannou's review, "Computational complexity of the quantum separability problem", (arXiv:quant-ph/0603199).
