If implemented properly, least-squares Monte Carlo as originally suggested by Longstaff-Schwartz should allow you to identify sub-optimal exercise dates and a lower bound of the true option price. There are many articles out there discussing this non trivial topic. @MarkJoshi can probably shed some more light, see this nice paper.
You claim that your LSM procedure overestimates the true option price: I guess that you did not use 2 independent set of paths i.e. one for calibrating the exercise boundary through regressions and a separate one for determining the exercise dates.
Regarding the precision of $5\%-20\%$, IMHO you must have a problem with your implementation. However, it is difficult to say anything more concerning your precision issue since you don't provide all the details: How many paths do you simulate and under what working modelling assumption, did you only use ITM paths during the regression pass, what type of basis functions did you choose and how many of them etc.