Perhaps this is just the operating systems course I took in college talking, but I recall that an operating system is defined not by the programs in user space, but rather by how everything is handled behind the scenes; in kernel space.
Process management, threads, interprocess communication, memory management, the file system structure, input/output, network primitives... Aren't these responsibilities of the operating system? All of these programs and low level interfaces are provided by the operating system, and thus by Linux and not by the GNU utilities.