Faits:
A. A.X._ et B.Z._, tous deux nés en 1969, sont unis par un mariage coutumier. Ils ont quatre enfants, C.X._, né en 1988, D.X._, né en 1990, E.X._, née en 1992 et F.X._, né en 1994.
En janvier 1999, A.X._ est entré en Suisse pour y déposer une demande d'asile. Il a indiqué être de nationalité yougoslave et a remis aux autorités helvétiques la copie d'un passeport de l'ex-République fédérale de Yougoslavie établi à son nom.
Le 3 mars 1999, l'Office fédéral des réfugiés (actuellement Office fédéral des migrations: ODM) a rendu une décision de non-entrée en matière sur la demande d'asile de A.X._ et a prononcé le renvoi de celui-ci de Suisse.
Le 7 janvier 2004, A.X._ et B.Z._ ont rempli un rapport d'arrivée à l'attention de l'autorité vaudoise de police des étrangers, indiquant être entrés en Suisse le 5 janvier 2004 avec leurs quatre enfants en provenance de Macédoine et n'être en possession d'aucune pièce de légitimation; ils ont affirmé être apatrides.
Le 23 mars 2004, A.X._ et B.Z._ ont déposé une demande de reconnaissance du statut d'apatrides auprès de l'ODM. A l'appui de leur requête, ils ont produit divers documents, notamment, concernant A.X._, les copies d'un extrait de registre de naissance émanant des autorités de la République de Macédoine, d'une attestation de la République de Serbie du 4 juillet 2002 certifiant que celui-ci n'était pas citoyen de cette République ni de la République fédérale de Yougoslavie et d'une décision du Ministère macédonien de l'intérieur du 30 juillet 2002 prononçant le rejet d'une demande de résidence et de naturalisation; pour B.Z._ et les 4 enfants, des copies d'extraits d'actes de naissance établis en 1997 à Prizren et en 2003 et 2004 à Vrsac, par les autorités de l'ex-République fédérale de Yougoslavie ont été remises. La famille a également transmis des copies de lettres de l'Ambassade de la République de Macédoine à Bonn du 2 juin 2000 indiquant, pour chacun de ses membres, ne pas pouvoir délivrer un document de voyage, car ceux-ci n'avaient pas la nationalité de cet Etat.
Le 28 juin 2004, l'ODM a indiqué que le Corps des gardes frontières de Bâle avait intercepté, en décembre 2003, un envoi postal en provenance d'Allemagne dans lequel se trouvait l'original d'un passeport provisoire macédonien, la copie d'un autre passeport établi en décembre 2002, la copie d'un passeport yougoslave et un acte de naissance macédonien. Comme ces documents, établis au nom de A.X._, ne paraissaient pas avoir été falsifiés, l'ODM a communiqué aux intéressés qu'il envisageait de ne pas entrer en matière sur leur demande tendant à la reconnaissance du statut d'apatrides.
Les requérants ont eu l'occasion de se prononcer sur ces documents. Ils ont relevé qu'ils accréditaient leur thèse selon laquelle ils avaient été ballottés d'un pays à l'autre, les autorités de Serbie et de Macédoine refusant de les reconnaître comme leurs ressortissants.
L'ODM a procédé à diverses investigations, demandant la collaboration de la Représentation suisse à Skopje. Il a obtenu en particulier la copie d'un acte de naissance et d'un acte de citoyenneté délivrés par les autorités de Skopje, au nom de A.X._ le 14 mars 2005. Les requérants ont pu se déterminer. Estimant que l'état de fait n'était pas suffisamment établi, ils ont précisé à l'attention de l'ODM qu'ils s'étaient adressés, le 11 mai 2005, au Ministère macédonien des affaires intérieures dans le but d'être formellement admis à vivre à Skopje, de pouvoir y bénéficier d'un appartement et des moyens d'existence nécessaires. Ils priaient l'ODM de bien vouloir s'enquérir auprès des autorités macédoniennes de la suite qu'elles entendaient donner à leur requête.
B. Par décision du 27 juin 2005, l'ODM a rejeté la demande tendant à considérer A.X._ et sa famille comme des apatrides. Il a retenu en bref qu'il ne résultait pas des pièces du dossier que les intéressés avaient été privés de leur nationalité et qu'ils ne pourraient la recouvrer. L'acte de naissance et de citoyenneté établis au nom de A.X._ en mars 2005 en fournissaient la preuve. Quant à B.Z._ et les quatre enfants, les actes de naissance datant de 1997, 2003 et 2004 reçus des autorités de Prizren et Vrsac leur permettaient de se faire établir des actes de citoyenneté desdites autorités.
Le recours contre cette décision, déposé le 14 juillet 2005 auprès du Département fédéral de justice et police, a été transmis au Tribunal administratif fédéral le 1er janvier 2007.
C. Par arrêt du 21 novembre 2007, le Tribunal administratif fédéral a rejeté le recours. Il a jugé qu'au vu des exigences strictes régissant la reconnaissance du statut d'apatrides, les documents versés au dossier ne suffisaient pas à démontrer que les recourants avaient perdu leur nationalité antérieure ou qu'ils avaient accompli toutes les démarches que l'on pouvait attendre d'eux pour la recouvrer.
D. Agissant par la voie du recours en matière de droit public, A.X._, B.Z._ et leurs enfants C.X._, D.X._, E.X._ et F.X._ concluent, avec suite de frais et dépens, à la réforme de l'arrêt du Tribunal administratif fédéral du 21 novembre 2007, en ce sens que le statut d'apatrides leur est reconnu ou, subsidiairement au renvoi de la cause pour nouvelles instruction et décision en ce qui concerne A.X._. Très subsidiairement, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause pour nouvelles instruction et décision. Ils demandent le bénéfice de l'assistance judiciaire.
Avec leur recours, ils produisent une attestation de l'Ambassade de Serbie à Berne du 27 décembre 2007, certifiant que, dans la mesure où les intéressés ne possèdent pas un certificat de nationalité serbe depuis six mois au maximum, ils ne peuvent pas obtenir un passeport de la République de Serbie.
Le Tribunal administratif fédéral renonce à se déterminer et l'ODM propose le rejet du recours en se référant à sa décision du 27 juin 2005.
Le 9 janvier 2008, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif formée par les recourants.

Considérant en droit:
1. Déposé contre un jugement rendu par le Tribunal administratif fédéral (<ref-law>) qui porte sur la reconnaissance du statut d'apatride, soit sur un domaine qui ne relève pas de l'une des exceptions mentionnées à l'art. 83 lettre c LTF, le présent recours est en principe recevable comme recours en matière de droit public.
Directement touchés par la décision attaquée, les recourants ont en outre un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), dès lors que, s'ils étaient reconnus comme apatrides au sens de la Convention du 28 septembre 1954 relative au statut des apatrides, ils auraient droit à une autorisation de séjour en Suisse et à des documents de voyage (voir art. 31 al. 1 et 59 al. 2 let. b de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RO 2007 p. 5437 ss).
Il convient donc d'entrer en matière.
2. 2.1 Le recours peut être formé pour violation du droit fédéral (<ref-law>), qui comprend les droits constitutionnels (<ref-ruling> consid. 3.1 p. 447). Saisi d'un tel recours, le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.2.2 p. 391, 249 consid. 1.2.2 p. 252) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>).
2.2 En vertu de l'<ref-law>, le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant. En ce domaine, les exigences en matière de motivation posées sous l'empire de l'art. 90 al. 1 let. b OJ demeurent valables (<ref-ruling> consid. 1.4.2; p. 254; Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 p. 4093 et 4142). Par conséquent, le recourant qui se plaint d'arbitraire ne peut se borner à critiquer la décision attaquée comme il le ferait en procédure d'appel, où l'autorité de recours jouit d'un libre pouvoir d'examen (<ref-ruling> consid. 1.3 p. 261); il ne peut se contenter d'opposer son opinion à celle de l'autorité inférieure, mais il doit démontrer, par une argumentation précise, que cette décision repose sur une application de la loi ou une appréciation des preuves manifestement insoutenables (<ref-ruling> consid. 3.2 p. 444).
2.3 En l'espèce, les recourants invoquent une violation des art. 5, 9, 29 al. 1, 35 et 36 Cst., ainsi que 6 CEDH, soit le droit d'être jugé de manière non arbitraire et équitable, mais ne motivent leurs griefs que sous l'angle de l'arbitraire. Le recours doit dès lors être examiné uniquement sur ce point et à la lumière des principes rappelés ci-dessus.
3. 3.1 Selon l'art. 1er de la Convention relative au statut des apatrides, conclue à New-York le 28 septembre 1954 (ci-après: la Convention; RS 0.142.40), le terme "apatride" désigne une personne qu'aucun Etat ne considère comme son ressortissant par application de sa législation. La question de savoir si ce terme vise seulement les personnes qui ont été privées de leur nationalité sans intervention de leur part ou également celles qui ont volontairement renoncé à leur nationalité ou se sont refusées, sans motifs valables, à entreprendre les démarches nécessaires pour recouvrer leur ancienne nationalité, n'est cependant pas réglée par la Convention.
3.2 Les autorités administratives suisses ne reconnaissent pas, en principe, le statut d'apatride au sens de l'art. 1er de la Convention aux personnes qui se laissent sciemment déchoir de leur nationalité. Tel est le cas notamment des personnes qui abandonnent leur nationalité durant une procédure d'asile vouée à l'échec, afin de bénéficier du statut privilégié d'apatride. L'Organisation des Nations Unies s'efforce en effet depuis longtemps de réduire au minimum les cas d'apatrides. La Convention sert au premier chef à aider les personnes défavorisées par le sort et qui, sans elle, seraient dans la détresse. Elle n'a pas pour but de permettre à toute personne qui le désire de bénéficier du statut d'apatride qui est, à certains égards, plus favorable que celui des autres étrangers (en matière d'assistance notamment). Reconnaître ainsi la qualité d'apatride à tout individu qui se laisserait déchoir de sa nationalité pour des raisons de convenances personnelles contreviendrait au but poursuivi par la communauté internationale. Cela équivaudrait, en outre, à favoriser un comportement abusif (arrêt 2A.78/2000 du 23 mai 2000, consid. 2b, non publié; voir également Samuel Werenfels, Der Begriff des Flüchtlings im schweizerischen Asylrecht, Diss. Bâle 1987, p. 130/131).
A la lumière de ces principes, le Tribunal fédéral en a déduit qu'il y a lieu d'interpréter l'art. 1er de la Convention en ce sens que, par apatrides, il faut entendre les personnes qui, sans intervention de leur part, ont été privées de leur nationalité et n'ont aucune possibilité de la recouvrer. A contrario, cette convention n'est pas applicable aux personnes qui abandonnent volontairement leur nationalité ou refusent, sans raisons valables, de la recouvrer, alors qu'ils ont la possibilité de le faire, dans le seul but d'obtenir le statut d'apatride (arrêt 2A.373/1993 du 4 juillet 1994, consid. 2c, non publié). Cette jurisprudence est depuis lors constante (arrêts non publiés 2A.153/2005 du 17 mars 2005, 2A.147/2002 du 27 juin 2002, 2A.78/2000 du 23 mai 2000; 2A.545/1998 du 15 mars 1999 et arrêt 2A.65/1996 du 3 octobre 1996, consid. 3c publié in JAAC 61/1997 no 74).
3.3 En l'espèce, le Tribunal administratif fédéral a estimé que les recourants ne remplissaient pas les conditions de la Convention et de la jurisprudence précitées pour être reconnus comme apatrides. Appréciant les pièces aux dossiers, les premiers juges ont constaté que A.X._ avait admis, lors de sa demande d'asile de 1999, être en possession d'un passeport de la République fédérale de Yougoslavie depuis 1991. Copie d'un tel document figurait d'ailleurs dans les pièces contenues dans le colis intercepté en 2003, de même que la copie d'un passeport macédonien établi en 2002 à son nom et valable dix ans. Or, les recourants, qui n'avaient jamais contesté l'authenticité de ces documents, n'avaient produit aucun élément propre à établir que A.X._ aurait été déchu, indépendamment de sa volonté, de la nationalité macédonienne. Au demeurant, les démarches de l'ODM, qui ont en particulier abouti à la délivrance d'un acte de naissance et de citoyenneté du 14 mars 2005, démontraient que A.X._ n'était pas privé de cette nationalité. D'ailleurs, même si cela était le cas, ce dernier n'avait à aucun moment établi avoir engagé des démarches auprès des autorités macédoniennes pour recouvrer sa nationalité et être dans l'impossibilité d'obtenir sa réintégration.
En ce qui concerne B.Z._ et les quatre enfants, le Tribunal administratif fédéral a retenu que ceux-ci étaient en possession d'extraits d'actes de naissance, établis par les autorités de l'ex-Serbie-et-Monténégro en 1997, 2003 et 2004. Il n'était pas davantage établi que les cinq requérants seraient privés, en regard de la législation serbe, de la faculté d'être officiellement reconnus comme des ressortissants de la Serbie, ni qu'ils auraient effectué toutes les démarches prescrites en vue de la reconnaissance de cette nationalité. En outre, les documents versés au dossier, notamment les attestations indiquant que l'un ou l'autre des intéressés n'est pas reconnu par les autorités de Serbie ou de Macédoine comme un ressortissant de l'Etat concerné, ne suffisaient pas à justifier la reconnaissance d'un statut d'apatride. Les premiers juges ayant ainsi forgé leur conviction, ils n'ont pas donné suite aux mesures probatoires proposées par les recourants.
4. Invoquant l'<ref-law>, les recourants reprochent au Tribunal administratif fédéral d'avoir établi des faits de manière insoutenable, soit d'avoir fait preuve d'arbitraire dans l'appréciation des pièces, en retenant que B.Z._ et ses quatre enfants n'ont jamais fourni d'éléments tendant à établir qu'il leur était exclu de pouvoir être officiellement reconnus comme ressortissants serbes. Ils se réfèrent à cet égard aux pièces 2 à 6 produites le 26 mai 2004, soit aux attestations de l'Ambassade de Macédoine à Bonn du 2 juin 2000, ainsi qu'à une pièce 12 produite le 21 octobre 2005, qui est une lettre dans laquelle l'Ambassadeur de Serbie-Montenegro à Berne confirme la teneur d'un entretien qui a eu lieu le 29 septembre 2005. Selon ce document, qui se référait aux faits présentés par les recourants pendant l'entretien et à un certificat de non-inscription dans les registres des citoyens de Serbie et Monténégro, les recourants ne remplissaient pas les conditions légales pour obtenir la nationalité de cet Etat.
4.1 D'après la jurisprudence, une décision est arbitraire lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une autre solution paraisse concevable, voire préférable; pour que cette décision soit annulée, encore faut-il qu'elle se révèle arbitraire, non seulement dans ses motifs, mais aussi dans son résultat (<ref-ruling> consid. 3.1 p. 153). Dans la mesure où l'arbitraire est invoqué en relation avec l'établissement des faits, il convient de rappeler que le juge dispose d'un large pouvoir lorsqu'il apprécie les preuves (<ref-ruling> consid. 4b p. 40). La partie recourante doit ainsi expliquer dans quelle mesure le juge a abusé de son pouvoir d'appréciation et, plus particulièrement, s'il a omis, sans aucune raison sérieuse, de prendre en compte un élément de preuve propre à modifier la décision attaquée, s'il s'est manifestement trompé sur son sens et sa portée ou encore si, en se fondant sur les éléments recueillis, il en a tiré des constatations insoutenables (<ref-ruling> consid. 2.1 p. 9 et la jurisprudence citée).
4.2 En l'espèce, le Tribunal administratif fédéral a considéré comme non pertinentes les attestations de l'Ambassade de la République de Macédoine à Bonn, celles-ci étant bien antérieures aux actes de naissance et de citoyenneté de A.X._, obtenus des autorités macédoniennes par la Représentation de Suisse à Skopje le 14 mars 2005. Dites attestations n'étaient pas non plus significatives pour B.Z._ et les quatre enfants, qui étaient en possession d'actes de naissance établis en 1997, 2003 et 2004 à Vrsac et à Prizren, en Serbie. Enfin, sorti de son contexte, l'entretien du 29 septembre 2005, qui a eu lieu à l'Ambassade de Serbie et Monténégro à Berne, ne permettait pas d'en conclure que B.Z._ et les quatre enfants avaient entrepris toutes les démarches prescrites par la législation serbe en vue de la reconnaissance de cette nationalité. Sur ce point, l'attestation du 27 septembre 2007 produite par les recourants, au demeurant irrecevable au regard de l'<ref-law>, ne fait qu'expliquer que, comme les recourants ne possèdent pas un certificat de nationalité serbe depuis six mois au maximum, ils ne peuvent obtenir un passeport de la République de Serbie. On ne saurait en déduire qu'ils n'auraient aucune possibilité de présenter une demande de reconnaissance ou de réintégration de leur nationalité. Même si le Tribunal administratif n'a pas précisé quelles démarches il aurait attendu que les recourants accomplissent au regard des législations serbes et macédoniennes, on ne peut en conclure qu'il a apprécié de façon insoutenable les éléments figurant au dossier, pour retenir que les pièces produites ne suffisaient pas à justifier la reconnaissance d'un statut d'apatride.
5. Les recourants reprochent aussi au Tribunal administratif fédéral de n'avoir pas donné suite à leurs offres de preuve tendant à démontrer la contradiction entre un document délivré à A.X._ le 25 décembre 2003, par lequel celui-ci s'est vu refuser la nationalité macédonienne, et l'acte de citoyenneté du 14 mars 2005, sur lequel les premiers juges se sont fondés. Ils estiment en effet que les autorités macédoniennes auraient dû à tout le moins fournir une explication sur cette contradiction, de même qu'elles auraient dû répondre à la demande de résidence et d'assistance en République de Macédoine qu'ils avaient formulée le 11 mai 2005. A leur avis, ce refus d'instruire se révèle non seulement discutable, mais véritablement arbitraire.
5.1 En procédure administrative fédérale, l'<ref-law>, applicable au Tribunal administratif fédéral par renvoi de l'<ref-law>, prévoit que l'autorité admet les moyens de preuve offerts par les parties s'ils paraissent propres à élucider les faits. Elle peut donc mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction, sans être liée par les offres de preuves des parties (cf. <ref-law> applicable en vertu de l'<ref-law>). Ces principes correspondent aux garanties posées par l'art. 29 al. 2 Cst., qui permet à l'autorité, par une appréciation anticipée des preuves, de renoncer à l'administration de certaines preuves offertes lorsque le juge parvient à la conclusion que les preuves offertes ne sont pas décisives ou qu'elles ne pourraient l'amener à modifier son opinion (cf. ATF 130 Il 425 consid. 2.1 p. 429; <ref-ruling> consid. 6c/cc p. 135, 417 consid. 7b p. 430). Au même titre que toute appréciation des preuves, l'appréciation anticipée de celles-ci est soumise à l'interdiction de l'arbitraire (<ref-ruling> consid. 5b p. 285 et les références citées).
5.2 Le Tribunal administratif fédéral a estimé qu'il était suffisamment renseigné et que rien ne justifiait les mesures complémentaires requises par les recourants. En effet, les autorités macédoniennes avaient donné suite aux démarches entreprises par la Représentation de Suisse à Skopje et établi, en 2005, un acte de naissance, ainsi qu'un acte de citoyenneté attestant formellement que A.X._ était de nationalité macédonienne. Quant à l'aménagement des conditions de résidence des recourants en Macédoine, il était sans importance au regard de la question de savoir si les intéressés pouvaient ou non se prévaloir de la qualité d'apatride au sens de l'art. 1er de la Convention. Ce raisonnement n'est pas insoutenable au vu des constatations ressortant du dossier, car l'on ne voit pas en quoi les moyens de preuves avancés par les recourants auraient été propres à fournir les éclaircissements nécessaires. Il ressort au contraire de l'ensemble des éléments présentés par les recourants, que tant les pièces qu'ils produisent, que les circonstances qu'ils décrivent, ne sont pas de nature à remettre en cause les attestations délivrées au sein même des pays concernés, ainsi que les documents d'identité établis au nom de A.X._ et découverts en décembre 2003.
Les premiers juges pouvaient donc admettre sans arbitraire que les recourants ne remplissaient pas les conditions posées par la jurisprudence pour être reconnus comme apatrides et renoncer ainsi à administrer leurs offres de preuve.
6. Au vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable.
Les recourants ont requis le bénéfice de l'assistance judiciaire. Compte tenu de leur situation financière précaire - qui leur a déjà permis d'obtenir l'assistance judiciaire devant le Tribunal administratif fédéral - et du fait que leurs conclusions ne paraissaient pas d'emblée vouées à l'échec, leur demande peut être admise (<ref-law>). Par conséquent, il y a lieu de les dispenser des frais et d'allouer une indemnité à leur mandataire, désigné comme avocat d'office (<ref-law>), sous réserve de remboursement ultérieur (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est admise.
3. Il n'est pas perçu de frais judiciaires.
4. La Caisse du Tribunal fédéral versera à Me Gilles Monnier une indemnité de 2'000 fr. à titre d'avocat d'office.
5. Le présent arrêt est communiqué au mandataire des recourants, à l'Office fédéral des migrations, au Tribunal administratif fédéral, Cour III, et, pour information, au Service de la population du canton de Vaud.
Lausanne, le 28 février 2008
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Merkli Rochat