I guess there are two questions here.
QUESTION 1: Skolem's Paradox shows that countability is relative in first-order logic, but where is the relativity? In this first question, I will do the following: (A) I will give an example here of the relativity of countability and then (B) talk about why I don't see the relativity. I am certain that what I write in (A) is right, but I am equally certain that I am wrong about what I write in (B). My question is where I am going wrong in (B). However, this might be a mathematical question, and almost certainly stems from my minimal understanding of set theory (although, I have been working for weeks trying to understand it).
(A) An example of the relativity of countability in first-order logic: Let A be an uncountable set in (a model) M. This means there is no bijection f in M between A and the set of naturals w. Now, add f to M and let this union be a new model N. Therefore, A is countable in N. So, whether a set A is countable or not is relative to what bijections with A some model recognizes.
(B) However, in order to talk about the model theory of set theory, we have to assume that set theory is consistent. Therefore, we must assume that there is some V (universe of sets) that serves as the model of set theory. Let's just use ZFC. Thus all the model theory we do on ZFC is done in V. That is, all models of ZFC that we look at are subsets of V. Now, it seems to me that this implies that there is an absolute perspective -- an ultimate arbiter of whether or not some set is countable. If A is countable according to V, then A is absolutely countable.
Indeed, some model M might not recognize a bijection between A and the set of naturals while V does (and thus A is absolutely countable), or M might also get the set of naturals wrong (i.e., it is not the same set that V sees as the set of naturals). Thus we can say from an absolute perspective whether a set A is (un)countable, whether some model is (un)countable, and we can say whether or not some model recognizes the right bijections or sets (e.g. is the set of naturals in M the same as V's?). And so, countability is not relative -- there is an absolute perspective, viz.: V's perspective.
Given (A) there is indeed a sense in which countability is relative, but it is (for lack of a better term) a local relativity: two models may differ on what they take to be w or f. But, this doesn't mean that countability is absolutely relative; again, isn't V the absolute perspective?
12 June 2012 EDIT: I asked about this at math.SE and the answer is simply that we don't just work in the universe. Sets that exist in the universe that are not in some model M under consideration are irrelevant for model theory in M -- at least, that's what I gathered.
QUESTION 2: Skolem's Paradox is not at all a problem for mathematics -- that is, no contradiction can be derived from (LS-Theorem ∧ Cantor's Theorem).
However, philosophers (I am told) still find the "paradox" interesting; they for some reasons find Skolem's Paradox still paradoxical, despite its not being a problem for mathematics. I ask: what are these reasons? why is it still paradoxical? why is it still philosophically interesting?