Hmmm, is it possible for you to share a project with us that has the problem. We haven't encountered it ourselves.
If possible please send the project to contact@esotericsoftware.com and include a link to this thread, or attach it here.
Sorry for the trouble!

Same problem here but with 120 vertices and 10 bones.

I wanted to push the tool as far as possible

A lot goes on for auto weights. We'll need a project that shows the problem. contact@esotericsoftware.com

I've had the same issue couple of times ever since the last update. However, in most of the cases, I got it working after retrying couple of times. It's frustrating nonetheless.

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?

I'll see if I can reproduce the bug somehow, so far I haven't encountered it though. A project that has the problem would go a long way for us to sort it.

Cool, I've replied to your email and we'll take a look at it, maybe we can figure out why it happens.

I can confirm this. Most of the time Spine refuses to autoweight the mesh. Haven't used it earlier so its hard to say if I am doing it in some "funny" way

Nate, Shiu - may be a better idea to solve this problem would be to talk about how the weight is calculated automatically looks like the search algorithm and how to properly build a grid?

Weight calculation is extremely complicated. It isn't the fault of how the mesh is defined, it's a problem with how I generate extra vertices to make the mesh more dense before computing the weights. I will definitely fix it, but have had more pursuing matters lately. I'll add a task on Trello.

I noticed that most of the time when I got Weights could not be computed, it was because the Weights button in the Tools bar was not selected.

I would go directly to the Weights window without selecting Weights from the Tools bar and when I select bind and then the bones and then auto, it would say weights could not be computed.

Try going to the Tools bar and select Weights. Make sure it has the blue selected color on the button. Then go into the Weights window and click bind and then the bones and then auto. See if that helps.

It didn't help me at all. It's an astoundingly frusturating problem. The auto-weighting (along with the meshes) is one of the features I purchased the Pro version for.

As far as I can tell, it's not about the vertices. It's about the bones. If you take the same mesh, same vertices, and subtract bones from the mesh, at some point the program tends to calculate appropriately.

Also, I just noticed that this problem is on the list of changes for "next up". So, allow me to say thanks, Nate.

Hi, any update on this? I encounter this daily and there is no workaround other than tweaking the bones aimlessly until it magically works. I can provide project files for debugging purposes if needed.

No update yet, but I know it's not something Nate forgot about. It might be helpful with the project file for debugging purposes so if you're willing to share it, please send it to contact@esotericsoftware.com with a reference to this thread.
Can't say when it will be looked into but hopefully it won't be too long. Sorry for the wait!

By the way ... sometimes you can get around this in another way. By unmaking the mesh (unchecking the mesh option), and then redoing it, the process for some reason seems to be completely reset, and the weights can be computed. It's all hinky and happenstance, though. So this is just a work around until the developers work out the kinks in the weighting algorithms.