I also encountered this issue (in QGIS 2.14.3 Essen), but Ale's answer didn't quite satisfy my requirements. I needed point geometry for all polygons (I couldn't delete any); having exact centres of the polygons was valuable because these were surveyed trees, and only the trunk diameters (as lines) were provided in the AutoCAD .dwg file I was using. Estimating the centres would introduce error and consume more time.
I first tried converting the lines to polygons (Vector -> Geometry Tools -> Lines to Polygons), a method I have used successfully in the past to get tree locations from line geometry into point geometry. This generated polygons for all the trees, but when trying to find the centres of these polygons, I encountered the "Error processing specified tolerance! Please choose larger tolerance..." error.
Following the logic in Ale's solution that the problem could be polygon size, I tried increasing the area of the polygons by adding a buffer (adding a "Buffer" column to the polygon shapefile attribute table, populating it with an arbitrary value of 5, and then using Vector -> Geoprocessing Tools -> Buffer to create a new polygon shapefile). The first polygonizing step had introduced geometry errors, though, so I didn't get polygons of all trees when trying to increase their sizes. Fixing the geometry errors would have consumed a lot of time, too, so I figured out something else.
To work around the issue, I ultimately buffered the original shapefile (the tree circles with line geometry) as outlined in the previous paragraph and then found the centres of those polygons. While I can't say if the real problem was polygon size and/or polygon geometry, it's clear that the buffer function produces larger polygons without introducing geometry errors, which can then be used to convert all polygons to points using the Polygon Centroids utility.