The "paradox" is really a contradiction of the axiom of unrestricted comprehension:
To every condition there corresponds a set of things meeting the condition.
Unrestricted comprehension allows you to build sets out of whole cloth, and seems reasonable. Of course everything divisible by two is a set, of course every prime number is a set. It's tempting to say that the set is simply defined by a single condition, and if some item fulfills that condition, it gets to be in the set.
Your example would not violate the axiom of unrestricted comprehension. No primes are divisible by 4, so the set of all primes divisible by 4 is the empty set. Russell's paradox does. He chose a condition that depends on the result of creating a set using that condition. "The set of all sets that do not contain themselves" can't contain itself, but it can't not contain itself either -- since either case would imply the opposite must be true.
The result is that unrestricted comprehension gets pared back. Instead of building a set from a condition, all sets must be built from a condition and a pre-existing set. A single infinite set corresponding to the natural numbers is given as an axiom, and all further sets (integers, real numbers, topological spaces, fields, and so on) are built from there.
Though, I think my example was misunderstood. I meant, why is it a problem that there is no set meeting Russell's definition, but not a problem that there is no number meeting my definition. The example would violate an axiom if there was an axiom like:
To every definition of a certain kind about natural numbers, there is a number which satisfies it.
Which of course would be rather useless, while the unrestricted comprehension axiom is necessary for the rest of the theory.
Your example would not violate the axiom of unrestricted comprehension. No primes are divisible by 4, so the set of all primes divisible by 4 is the empty set. Russell's paradox does. He chose a condition that depends on the result of creating a set using that condition. "The set of all sets that do not contain themselves" can't contain itself, but it can't not contain itself either -- since either case would imply the opposite must be true.
The result is that unrestricted comprehension gets pared back. Instead of building a set from a condition, all sets must be built from a condition and a pre-existing set. A single infinite set corresponding to the natural numbers is given as an axiom, and all further sets (integers, real numbers, topological spaces, fields, and so on) are built from there.