So it would seem that the primality is complete red herring here if using all natural numbers (and especially all odd natural numbers) also draws similar parallelograms?

If so then I feel bit disappointed that numberphile went with just the story that "wooo prime numbers are weird"

I think primes make interesting patterns in every base. With all the numbers you must change the filtration rules in each base to get a nice graph. (Also, the primes have the side effect of producing a nice texture.)

A while ago, I found that hailstone numbers make an interesting pattern, and the graph I made got exponentially more difficult to generate the further it went, so it motivated me to experiment a little with AWS for some additional computing power.