1. People use bad PRNGs or otherwise mess this up so the nonces aren’t as random as they should be, or they use ciphers with small nonce spaces (eg original ChaCha with 64-bit nonces) and generate enough nonces that collisions become likely.
2. Even if you use a larger nonce space, like GCM’s usual 96-bits, you may be Google and generate so many nonces so quickly that collisions even then become likely. (This is generally not a problem for >128 bit nonces though). See the rationale for the development of AES-GCM-SIV for an example.
3. If you generate a random nonce then you have to send that nonce on the wire, which adds overhead (e.g. 16 bytes per message). If you send a lot of small messages or have strict space limits then you might not want this overhead, leading back to deterministic nonce generation.
4. There are a lot of existing crypto protocols in use, and almost all of them use deterministic nonces. We’re not going to just replace them all overnight with random nonce variants.