Was the slapadd given -w option? I don't think it's strictly necessary, but it should let syncprov figure things out faster.