In this paper, we study the $k$-error linear complexity of binary sequences with periods $p^n$, which are derived from new generalized cyclotomic classes modulo a power of an odd prime $p$. We establish a recursive relation and then estimate the $k$-error linear complexity of the binary sequences with periods $p^n$, the results extend the case $p^2$ that has been studied in an earlier work of Wu et al. at 2019. Our results show that the $k$-error linear complexity of these sequences does not decrease dramatically for $k<(p^n-p^{n-1})/2$.