Why do miners need a nonce if the timestamp changes the hash of the block?
Is it because they're mining too fast for the timestamp to change?


Precisely - even a relatively slow CPU can hash several hundred headers every second. Modern day ASICs can hit 100+ terahashes per second - ripping through the entire nonce space several times over.

Moreover, the timestamp is also a 4 byte value - miners do use it, in conjunction with the nonce, merkle root, and block version to create a much larger search space. Even so, the majority of combinations of all of these do not result in valid blocks.