Sachverhalt:
A. Der aus dem Kosovo stammende X._ (geb. 1964) hatte im Jahre 1990 in seiner Heimat die Landsfrau A._ geheiratet und mit ihr die beiden Kinder B._ (geb. 1991) und C._ (geb. 1994) gezeugt. Zwischen 1991 bis 1996 hielt er sich als Saisonnier in der Schweiz auf. Seine Ehe wurde am 25. Februar 1997 geschieden, worauf er ohne gültiges Visum wieder in die Schweiz gelangte und am 11. April 1997 D._ - eine Schweizerin kosovarischer Herkunft - heiratete. In der Folge erhielt er eine Aufenthaltsbewilligung, welche mehrmals verlängert wurde. Nachdem er am 19. Juli 2001 gestützt auf Art. 27 des Bundesgesetzes vom 29. September 1952 über Erwerb und Verlust des Schweizer Bürgerrechts (Bürgerrechtsgesetz, BüG; SR 141.0) erleichtert eingebürgert worden war, reichten die Eheleute im darauffolgenden November ein gemeinsames Scheidungsbegehren ein, worauf die Ehe am 18. April 2002 vom Bezirksgericht Zürich geschieden wurde. Am 27. November 2002 heiratete X._ im Kosovo seine erste Ehefrau A._ wieder und stellte für sie und die beiden gemeinsamen Kinder am 21. Juni 2003 im Kanton Zürich ein Familiennachzugsgesuch.
B. Am 17. Januar 2005 erklärte das Bundesamt für Migration die erleichterte Einbürgerung von X._ für nichtig. Das Bundesgericht bestätigte diese Verfügung letztinstanzlich mit Urteil vom 7. Mai 2007 im Verfahren 5A.37/2006.
C. Am 4. April 2008 stellte X._ ein Gesuch um Erteilung der Niederlassungs- bzw. Aufenthaltsbewilligung und erneuerte sein Gesuch um Familiennachzug für A._ und die beiden gemeinsamen Kinder. Mit Verfügung vom 26. Januar 2009 wies die Sicherheitsdirektion des Kantons Zürich (Migrationsamt) die Gesuche ab. Es erwog im Wesentlichen, X._ und D._ seien die Ehe nur zum Schein eingegangen. Der gegen diese Verfügung beim Regierungsrat des Kantons Zürich erhobene Rekurs blieb erfolglos, und mit Urteil vom 3. Februar 2010 (versandt am 16. März 2010) wies das Verwaltungsgericht des Kantons Zürich die gegen den regierungsrätlichen Beschluss vom 19. August 2009 erhobene Beschwerde ebenfalls ab.
D. Mit Eingabe vom 3. Mai 2010 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das letztgenannte Urteil des Verwaltungsgerichts und die ihm zugrunde liegenden Entscheide aufzuheben und ihm - dem Beschwerdeführer - sowohl die Niederlassungsbewilligung zu erteilen als auch den Familiennachzug zu bewilligen; eventuell sei ihm die Aufenthaltsbewilligung zu erteilen, subeventuell die Sache zur Durchführung weiterer "Sachabklärungen" zurückzuweisen. Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht.
Die Sicherheitsdirektion des Kantons Zürich hat sich nicht vernehmen lassen. Das Verwaltungsgericht des Kantons Zürich schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Migration beantragt, die Beschwerde abzuweisen.
E. Mit Verfügung vom 19. Mai 2010 hat der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Am 1. Januar 2008 hat das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) abgelöst. Dem Beschwerdeführer war - gestützt auf die Ehe mit D._ - seinerzeit (1997) die Aufenthaltsbewilligung noch gestützt auf Art. 7 Abs. 1 ANAG erteilt worden, wonach der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung bzw. nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren Anspruch auf die Niederlassungsbewilligung hat. Mit der - rechtskräftigen - Nichtigerklärung der Einbürgerung wurde er ausländerrechtlich in die gleiche Rechtsstellung wie vor der Einbürgerung versetzt, und es ist aufgrund der aktuellen Sachlage neu über sein allfälliges Anwesenheitsrecht zu entscheiden (vgl. <ref-ruling> E. 3.2 S. 5f). Er hat sein Gesuch um Erteilung der Niederlassungs- bzw. Aufenthaltsbewilligung/Familiennachzug nach Inkrafttreten des AuG gestellt (4. April 2008). Für die Beurteilung der vorliegenden Streitsache gilt demnach das neue Ausländerrecht (Art. 126 Abs. 1 AuG e contrario).
1.2 Ausländische Ehegatten von Schweizerinnen und Schweizern haben Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen (Art. 42 Abs. 1 AuG); nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren haben die Ehegatten Anspruch auf Erteilung der Niederlassungsbewilligung (Art. 42 Abs. 3 AuG). Der Beschwerdeführer hat nach erfolgter Scheidung zwar keinen Anspruch mehr auf Verlängerung seiner Aufenthaltsbewilligung nach Art. 42 Abs. 1 AuG. Er war jedoch mehr als fünf Jahre mit einer Schweizerin verheiratet. Sollte er vor der Scheidung einen Anspruch auf die Niederlassungsbewilligung erworben haben, kann er sich nach der Rechtsprechung hierauf auch nach der Beendigung der Ehe berufen (<ref-ruling> E. 1.1.4 S. 149). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist insoweit zulässig (Art. 83 lit. c Ziff. 2 AuG e contrario). Dies gilt auch für den vom Beschwerdeführer eingenommenen Eventualstandpunkt, mit dem er die Erteilung einer Aufenthaltsbewilligung verlangt (vgl. dazu Art. 50 AuG).
Unzulässig ist das Rechtsmittel hingegen, soweit es sich gegen die kantonal vorinstanzlichen Entscheide richtet, da diese durch das verwaltungsgerichtliche Urteil ersetzt worden sind und als mitangefochten gelten (sog. Devolutiveffekt; vgl. <ref-ruling> E. 1.4 S. 144; <ref-ruling> E. 1 S. 441).
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Die Rüge des Beschwerdeführers, die Vorinstanzen hätten die Begründungspflicht und damit den Gehörsanspruch verletzt (vgl. Beschwerdeschrift S. 4 und 6), erweist sich vorab als unbegründet: Aus dem Anspruch auf rechtliches Gehör nach <ref-law> folgt zwar in der Tat die grundsätzliche Pflicht der Behörde, ihren Entscheid zu begründen. Das bedeutet indessen nicht, dass sich die Behörde mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Der Bürger soll wissen, warum die Behörde entgegen seinem Antrag entschieden hat, damit er gegebenenfalls den Entscheid sachgerecht anfechten kann (<ref-ruling> E. 3.1 S. 277 mit Hinweisen). Diesen Anforderungen genügt der vorinstanzliche Entscheid.
3. 3.1 Gemäss Art. 51 Abs. 1 lit. a und Art. 51 Abs. 2 lit. a AuG erlöschen die Ansprüche nach Art. 42 und Art. 50, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen zu umgehen. Erfasst wird davon die sogenannte Scheinehe bzw. Ausländerrechtsehe. Ein Bewilligungsanspruch entfällt demnach, wenn zum Vornherein nie der Wille bestand, eine dauerhafte Gemeinschaft zu begründen, und der einzige Zweck der Heirat darin liegt, dem Ausländer zu einer fremdenpolizeilichen Bewilligung zu verhelfen (vgl. <ref-ruling> E. 2.1 S. 151 mit Hinweisen).
3.2 Das Vorliegen einer Ausländerrechtsehe darf nicht leichthin angenommen werden (vgl. <ref-ruling> E. 2.2 S. 151). Es ist Sache der Fremdenpolizeibehörden, eine Scheinehe nachzuweisen. Dabei müssen die Behörden den Sachverhalt grundsätzlich von Amtes wegen untersuchen. Der Untersuchungsgrundsatz wird aber durch die Mitwirkungspflicht der Parteien relativiert. Diese kommt naturgemäss gerade für solche Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden können (vgl. Urteil 2C_799/2010 vom 20. Februar 2011 E. 2.3 mit Hinweis; vgl. zur Mitwirkungspflicht: <ref-ruling> E. 3.2 S. 115; <ref-ruling> E. 2b S. 365; <ref-ruling> E. 4c/cc S. 394). Das gilt umso mehr, wenn gewichtige Hinweise für eine Ausländerrechtsehe sprechen; dann kann von den Eheleuten erwartet werden, dass sie von sich aus Umstände vorbringen, die den echten Ehewillen belegen.
3.3 Ob eine Scheinehe geschlossen wurde, entzieht sich in der Regel dem direkten Beweis und ist bloss durch Indizien zu erstellen (<ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweis). Feststellungen des kantonalen Richters über das Bestehen von solchen Hinweisen können äussere Gegebenheiten, aber auch innere psychische Vorgänge betreffen (Wille der Ehegatten). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. E. 1.3; <ref-ruling> E. 1.4.3 S. 254 f.). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (<ref-ruling> E. 2.3 S. 152 mit Hinweisen). Für die Annahme einer Scheinehe bedarf es konkreter Hinweise darauf, dass die Ehegatten nicht eine eigentliche Lebensgemeinschaft führen wollen, sondern die Ehe nur aus fremdenpolizeilichen Überlegungen geschlossen haben. Diesbezügliche Indizien lassen sich unter anderem darin erblicken, dass dem Ausländer die Wegweisung drohte, etwa weil er ohne Heirat keine Aufenthaltsbewilligung erhalten hätte oder sie ihm nicht verlängert worden wäre. Für das Vorliegen einer Ausländerrechtsehe können sodann die Umstände und die kurze Dauer der Bekanntschaft sprechen sowie insbesondere die Tatsache, dass die Ehegatten eine Wohngemeinschaft gar nie aufgenommen haben. Dasselbe gilt, wenn für die Heirat eine Bezahlung vereinbart wurde oder wenn ein erheblicher Altersunterschied zwischen den Ehepartnern besteht. Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, kann umgekehrt nicht schon daraus abgeleitet werden, dass die Ehegatten während einer gewissen Zeit zusammenlebten und intime Beziehungen unterhielten; ein derartiges Verhalten kann auch nur vorgespiegelt sein, um die Behörden zu täuschen (<ref-ruling> E. 2b S. 295 mit Hinweisen). Eine Scheinehe liegt demgegenüber nicht bereits dann vor, wenn ausländerrechtliche Motive für den Eheschluss mitentscheidend waren. Erforderlich ist zusätzlich, dass der Wille zur Führung einer Lebensgemeinschaft - zumindest bei einem der Ehepartner - von Anfang an nicht gegeben ist (<ref-ruling> E. 2.1 S. 151; <ref-ruling> E. 4 und E. 5 S. 55 ff.).
4. 4.1 Das Verwaltungsgericht stellte - zum Teil unter Verweis auf den regierungsrätlichen Beschluss - fest, der Beschwerdeführer habe 1997 nicht mehr mit einer Anwesenheitsberechtigung in der Schweiz rechnen können. Die unmittelbar nach der illegalen Einreise erfolgte Heirat mit einer Schweizerin stelle ein gewichtiges Indiz für einen Eheschluss zum Zweck der Umgehung ausländerrechtlicher Vorschriften dar. Dass sich die Ehefrau weder an das Hochzeitsjahr noch an den Hochzeitsort noch an den Namen der Trauzeugin zu erinnern vermöge, deute darauf hin, dass es sich bei dieser Hochzeit um eine rein formelle Angelegenheit gehandelt habe. Auch später habe sich die Beziehung nicht intensiviert, sei doch der Ehefrau weder die Namen noch das Alter ihrer beiden Stiefsöhne bekannt gewesen. Besonders mit Blick auf die zeitliche Abfolge der einzelnen Ereignisse müsse geschlossen werden, dass es sich bei der hier zu beurteilenden Ehe um eine Scheinehe gehandelt habe.
4.2 Der Beschwerdeführer hält die Sachverhaltsermittlung und Beweiswürdigung durch die kantonalen Instanzen für willkürlich. Er macht geltend, im Verfahren betreffend Nichtigerklärung der Einbürgerung sei - zu Recht - nie von einer Scheinehe die Rede gewesen. Die Eheleute hätten vielmehr jahrelang in ehelicher Gemeinschaft zusammengelebt. Gerade nicht ausländerrechtliche Beweggründe, sondern die psychische Erkrankung der Eheleute habe schliesslich dazu geführt, dass die Ehe gescheitert sei und der Beschwerdeführer sich wieder der ersten Ehefrau angenähert habe; Beweise hierfür (namentlich die Befragung von Zeugen) habe die Vorinstanz willkürlich übergangen. Dass D._ nicht alle Daten zur Hochzeit habe nennen können, sei ebenfalls mit ihren psychischen Problemen zu erklären und kein Indiz für eine Scheinehe; schliesslich sei der Vorschlag, die Ehe einzugehen, auch von ihr und nicht vom Beschwerdeführer gekommen. Aufgrund des tatsächlichen Sachverhalts und der klaren Rechtslage sei dem Beschwerdeführer daher nicht nur Aufenthalt und Familiennachzug zu bewilligen, sondern auch die Niederlassungsbewilligung zu erteilen.
4.3 Die Einwendungen des Beschwerdeführers sind nicht geeignet, die tatsächlichen Feststellungen des Verwaltungsgerichts als offensichtlich unvollständig bzw. unrichtig und die von ihm daraus gezogenen rechtlichen Schlussfolgerungen als bundesrechtswidrig erscheinen zu lassen: Zunächst hat das Verwaltungsgericht die psychischen Probleme von D._, mit denen der Beschwerdeführer deren Wissenslücken zu Ehe und Familie zu erklären versucht, nicht übersehen, sondern im Rahmen der Gesamtwürdigung der Indizien berücksichtigt (vgl. S. 6 des angefochtenen Entscheides). Schon die nach aussen wahrnehmbare Vorgehensweise des Beschwerdeführers stellt sodann für sich allein ein gewichtiges Indiz dar, dass es den Eheleuten von Anfang an am Willen fehlte, eine echte eheliche Lebensgemeinschaft zu führen: Er liess sich, nachdem er keine Aussicht auf eine weitere Saison-Bewilligung für die Schweiz mehr hatte, nach rund siebenjähriger Ehedauer von der Mutter seiner beiden kleinen Söhne scheiden, heiratete weniger als zwei Monate nach der Scheidung D._ und stellte zum frühestmöglichen Zeitpunkt ein Gesuch um erleichterte Einbürgerung. Kurz nachdem er das Bürgerrecht erlangt hatte, kam es zur Scheidung auf gemeinsames Begehren; der Beschwerdeführer heiratete seine geschiedene Ehefrau wieder und beantragte schliesslich den Familiennachzug für sie und die gemeinsamen Kinder. Auch aus den anderen vorhandenen Akten - namentlich aus den Befragungsprotokollen - durften sowohl der Regierungsrat wie auch das Verwaltungsgericht willkürfrei auf einen fehlenden echten Ehewillen schliessen; die Aussage der Ehefrau ("Ich bin ja hier in der Schweiz, er ist ein super netter Mensch und ich brauchte einen Schutz, der nicht zulässt, dass mir jemand etwas antut, ich hatte auch psychische Probleme ") sowie der Umstand, dass der Vorschlag für eine Heirat offenbar von ihr gekommen sein soll, entkräftet eine solche Schlussfolgerung gerade nicht, ebenso wenig die geltend gemachten beiden Schwangerschaften, welche nach unbestrittener Darstellung im Beschluss des Regierungsrates in eine Fehlgeburt (Juni 1998) und in eine Abtreibung (Februar 1999) mündeten. Dass die Ehegatten am 25. Juni 2001 noch eine gemeinsame Erklärung unterzeichnet hatten, wonach sie in einer tatsächlichen, stabilen ehelichen Gemeinschaft zusammenlebten, vermag ebenfalls nichts zu ändern: Einerseits steht diese Erklärung im Widerspruch zur Aussage von D._ vom 20. August 1999 gegenüber dem Betreibungsamt Geroldswil, wonach sie - nicht viel mehr als zwei Jahre nach der Eheschliessung - von ihrem Ehemann bereits getrennt lebe und dieser sich in Zürich aufhalte. Andererseits wurde die Erklärung im Rahmen der - später für nichtig erklärten (vorne lit. "B") - erleichterten Einbürgerung des Beschwerdeführers abgegeben, so dass sie im Rahmen der Würdigung der Indizien entsprechend geringes Gewicht erhält. Zudem war in jenem Verfahren einzig massgebend, ob im Zeitpunkt der Einbürgerung noch ein auf die Zukunft gerichteter Ehewille bestand; der Frage, ob von Anfang an eine Scheinehe vorlag, war nicht weiter nachzugehen.
Wenn Regierungsrat und Verwaltungsgericht aufgrund der vorhandenen Indizienlage vorliegend auf eine Schein-/bzw. Ausländerrechtsehe geschlossen haben, ist dies nach dem Gesagten nicht zu beanstanden; auf weitere Beweiserhebungen durfte verzichtet werden, ohne in Willkür zu verfallen (vgl. <ref-ruling> E. 2.1 S. 428; <ref-ruling> E. 4a S. 211).
4.4 Der Beschwerdeführer beruft sich sodann vergeblich auf Art. 50 Abs. 1 lit. a AuG, wonach er auch nach Auflösung der Ehe nach dreijähriger Ehegemeinschaft Anspruch auf eine Aufenthaltsbewilligung habe und ihm - der mehr als fünf Jahre mit D._ verheiratet gewesen sei - zumindest eine solche zu erteilen sei: Auf die Regel von Art. 50 Abs. 1 lit. a AuG käme es nur an, wenn der Ehewille erst nachträglich - d.h. hier kurz vor der erleichterten Einbürgerung des Beschwerdeführers - entfallen wäre, nicht jedoch, wenn von Anfang an auf eine Schein- bzw. Ausländerrechtsehe zu schliessen war (vgl. Art. 50 Abs. 2 lit. a AuG).
5. Nach dem Gesagten besteht für den Beschwerdeführer in der Schweiz kein Anwesenheitsanspruch, zumal - wie das Verwaltungsgericht zutreffend festgestellt hat (S. 8 des angefochtenen Entscheides) - besonders intensive, über eine normale Integration hinausgehende private Bindungen des Beschwerdeführers zur oder in der Schweiz, welche ihm allenfalls ein Anwesenheitsrecht gestützt auf die Garantie der Achtung des Privatlebens (Art. 8 EMRK) verschaffen könnten (vgl. <ref-ruling> E. 3.2.1) ebenfalls weder dargetan noch ersichtlich sind.
Soweit sich der Beschwerdeführer unter Hinweis auf seine behandlungsbedürftigen Depressionen allenfalls auf eine Bewilligung des Aufenthalts nach Art. 30 Abs. 1 lit. b AuG (allgemeiner ausländerrechtlicher Härtefall) berufen will, besteht hierauf ebenfalls kein Anspruch, weshalb das Bundesgericht dies hier nicht zu prüfen hat.
Steht dem Beschwerdeführer aber kein Anspruch auf eine Anwesenheitsbewilligung zu, entfällt auch jede Grundlage für entsprechende Ansprüche seiner wieder geheirateten Ehefrau und der beiden gemeinsamen Kinder.
6. Die Beschwerde ist als unbegründet abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang wird der Beschwerdeführer kostenpflichtig: Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann schon aufgrund des fehlenden Nachweises seiner Mittellosigkeit (<ref-law>) nicht entsprochen werden; die drei eingereichten Belege über den Bezug von Arbeitslosentaggeldern zwischen März und Mai 2010 genügen für eine erschöpfende Auskunft über die finanziellen Verhältnisse offensichtlich nicht (vgl. Schreiben des Abteilungspräsidenten vom 18. Mai 2010).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht (2. Kammer) des Kantons Zürich und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 25. Juli 2011
Der Präsident: Der Gerichtsschreiber:
Zünd Klopfenstein