I wouldn't say they rewrote the GNU utilities. BSD's lineage goes back farther than GNU's, they were at least at BSD4.1 before Stallman started GNU. There was an established userland. I imagine there's some GNU utility that was sort of "clean roomed" into *BSD, but that would be the exception, not the rule.