I think it's about the fact that they are a mystery at the heart of maths. You can start describing maths from the unit, the addition and the negative sign. If you start combining those, you get the natural numbers, the integers, ... but even before the natural numbers come the prime numbers. Primes are the most fundamental set of numbers in mathematics, from which you can generate the natural numbers.

But as you say, even after so many years they are still relevant, useful and mysterious. They are on a wildly different category from other sets and numerical series. They are the most central element of maths that we still don't understand. And central means that so many other parts of maths derive from it, and therefore we end up coming across prime numbers everywhere. We use them to analyze so many other parts of maths, but yet they remain elusive to analysis themselves. It's a fundamental, recurrent mystery that's also an extremely useful tool... one of the most beautiful things we know.