Apt-get hangs on "Setting up mysql-server-5.5 (5.5.44-0+deb8u1)"

This was very odd. Two hours ago I left my computer with apt-get still running. I just came back to see that setting up had finally finished. Before, I had waited maybe 15-30 minutes, so this is certainly not normal. But now I can purge the package and reinstall it within seconds.

So, the solution to this seems to simply be "wait". It works itself out in the end.