Many of those did need something approaching a rewrite and even got one of sorts, but just were big enough that there was plenty that was unaffected by whatever big change was needed.

The Linux kernel for instance gets big changes. The BKL took a very long time to fully remove.

The GNU utils needing a rewrite would be weird since most of them implement a pre-existing standard, so the need for a huge rewrite is very unlikely.