Are you using shutil.copytree()?
I've notice that quite often lock files persist in the FGDB folders (even after all the featurelayers, tableviews, cursor refs, etc are deleted). In that case, I have had to rely on the (frankly much slower) gp.Copy_management() tool.