How do you validate a scientific paper that uses a non-public cell/animal line? Recently my lab published a paper that uses a mouse line from another lab.

Without going into too much detail since not everyone here is a Biologist, this other lab has a mouse with a reporter gene in it for hetero/euchromatin formation (DNA "openness"). This took them a long time (and a lot of work) to create. Basically, if the chromatin structure changes significantly in the mouse, this reporter gene is activated. Tens of thousands of these mice are then randomly mutated, and if a mutation happens to cause a big change in the chromatin openness, their reporter gene flashes up, and the mouse is given an ID and becomes it's own little mouse line to study why/how the DNA openness changed.

My lab was given a few individuals from one of these mutated mice lines - enough to start our own breeding colonies. However, there were some restrictions on what we could do - we can't reverse-engineer the reporter construct, we can't use the reporter construct ourselves for anything, and we obviously can't give the mice to any other labs. We can only examine the phenotype (and find the causative mutation).

Now our work on the phenotype has been published (quite highly in a major journal), and i'm interested to know how Science is supposed to validate such experiments?

I presume my lab still cannot give out the mice we used to generate our data to other labs.
I presume that the lab we got our mice from is under no obligation to give out their mice either - and they may not want to since it would contain their reporter.

So I presume this means the results cannot be validated by anyone else without them going through the whole process of creating a new mutant mouse line first (and even then, it doesn't speak to the validity of the data on our mice).
You've published the results in a prestigious journal.  In most of those journals, that means you've promised to make those mice available to other researchers.  For example, Nature says

An inherent principle of publication is that others should be able to replicate and build upon the authors' published claims. A condition of publication in a Nature journal is that authors are required to make materials, data, code, and associated protocols promptly available to readers without undue qualifications.

(Emphasis in the original)
Science says

After publication, all data and materials necessary to understand, assess, and extend the conclusions of the manuscript must be available to any reader of Science.

Similar verbiage is in most high-quality journals.  Typically, you agree to those conditions when you submit, or when your paper is accepted, by agreeing with and/or signing forms.
So you may not have known it, but you have already promised to make those mice available.  Do you feel that you can't do that?  Then you shouldn't have agreed to do so when you published.  If someone requests the mice, and you refuse in spite of your agreement, you may end up being blackballed by the publisher and may never publish with them again.  Conceivably -- though I haven't heard of cases reaching this point -- your article could be retracted over your objections, or you could face an academic dishonesty investigation.
(The same applies to the original researchers who made the mice, of course, and in practice most researchers would consider the onus to be on them, not you, to provide the mice.  But that's a pragmatic thing. As I say, you've most likely already explicitly guaranteed that you will make the mice available on request, and it's your problem to make good your promise.)
Edit to point to an even more explicit explanation from the NIH, in the Grants and Funding section, Frequently Asked Questions: Sharing of Model Organism and Related Resources:

What is NIH policy regarding the distribution and sharing of mutant strains of model organisms created with NIH funds?
The NIH expects that new, genetically modified model organisms and related resources generated with the aid of NIH funding will be distributed and shared with the scientific community in a timely way, generally at least upon publication of the primary results announcing the development of the genetically modified model organisms. Investigators submitting an NIH application (including competing renewals) are expected to include a concise plan addressing the timely distribution of organisms and resources, unless the proposed research will not generate new model organisms and related resources.

Question 9 is particularly relevant here:

... I don’t want to share my novel animal strains or the reagents used to make them. Can I be forced to do so?
Sharing of research resources is a very important NIH policy and is included as a term and condition of your award.

(My emphasis)
So not only have you agreed to make the mice available when you agreed to the publication terms, if your work was NIH-funded, you also already promised to make them available, even if you don't want to.
That section notes that there are possible reasons for not sharing, and the NIH will consider them, but they must be explicitly stated in the grant (and putting that in your grant will make it less likely to be funded).  If it was not explicitly stated in the grant originally, this is not an acceptable excuse.
Other granting agencies have similar policies.