That's not true, at least for the even number apart example.
The prime method will sample songs p apart from each other, and it's easy to find examples of N and p where p is even, for example N=5 p=2. More generally, this method works for any n that is co-prime with N, so N=5 n=4 works as well.
There are lots of shufflings where subsequent songs are not separated by a constant amount, so your main point is true. There are many combinations of songs that you would never hear no matter which prime you picked.
To quantify just how many takes a little bit of work.
There are N! total shufflings possible. We know that there are N-1 or less numbers that are co-prime with N (you get N-1 when N is prime, less otherwise). For each number that is co-prime, we have N possible shufflings, each starting from a different point. This gives at most N(N-1) shufflings from the prime method (really the co-prime method).
As a percentage of total shufflings, we know the upper bound from the co-prime method is N(N-1) / N! == 1/(N-2)!. This very quickly goes to 0. For the first few N,
N % of shuffles
2 100.00000%
3 100.00000%
4 50.00000%
5 16.66667%
6 4.16667%
7 0.83333%
8 0.13889%
9 0.01984%
10 0.00248%
11 0.00028%
12 0.00003%
13 0.00000%
So for any reasonable number of songs, we know that _most_ shufflings will not be found by the prime shuffling method.