I am getting this error frequently too, now that we are in version 2 of spine.
One thing I think contributes to it is that we can have the weights window thing be available at all times. When I click on my mesh and click bind in the weights window WITHOUT selecting weights in the tool bar, and then click the bones I want and click auto, it says weights could not be computed almost immediately.
If I select weights from the toolbar, and then click bind from the weights window, and choose the bones and click auto, the weights are more likely to be computed. They do not always get computed but it's more likely.
If there was a way for the weights button in the toolbar to be automatically selected when you click on the bind in the weights window, would that help this issue?