Sachverhalt: A. X._ (geb. 1972) stammt aus dem Kosovo. In den Jahren 1992 und 1997 suchte er erfolglos um Asyl nach und wurde nach Abschluss dieser Verfahren jeweils aus der Schweiz weggewiesen. 1998 reichte er ein weiteres Asylgesuch sein, welches als gegenstandslos abgeschrieben wurde, nachdem er 1999 eine ursprünglich aus Thailand stammende Schweizerin (geb. 1955) geheiratet hatte. Im Mai 2005 erlangte X._ die Niederlassungsbewilligung. Im November desselben Jahres trennten sich die Eheleute, im Juni 2006 liessen sie sich scheiden. Im Juli 2006 heiratete X._ im Kosovo Y._ (geb. 1975) und stellte am 2. Oktober 2006 ein Gesuch um Familiennachzug zugunsten seiner zweiten Ehefrau und deren Kinder A._ (geb. 2002) und B._ (geb. 2003). Dabei wurde erklärt, die Kinder seien ausserehelich geboren, je mit unbekanntem Vater. B. Die soeben geschilderte Geschehensabfolge erweckte bei den Migrationsbehörden den Verdacht, X._ könnte mit seiner zweiten Frau bereits während der ersten Ehe eine Paarbeziehung gepflegt haben und er sei womöglich der Vater der Kinder A._ und B._. Dies führte zu verschiedenen Abklärungen hinsichtlich des beantragten Familiennachzugs. Namentlich wurde Y._ in der Schweizer Vertretung in Pristina zur Sache angehört; dabei verweigerte sie die Einwilligung in eine DNA-Analyse zur Ermittlung der Vaterschaft X._s. Dieser seinerseits stimmte einer solchen Untersuchung im März 2007 zunächst zu, widerrief dieses Einverständnis aber wenig später wieder, um sich im Juni 2007 erneut damit einverstanden zu erklären. Am 11. Mai 2007 wurde den Eheleuten X._ und Y._ der Sohn C._ geboren. In der Folge erhielten Y._ und die drei Kinder ein auf drei Monate beschränktes Besuchsvisum für die Schweiz zwecks Abklärung der familiären Verhältnisse, der Y._ unterdessen zugestimmt hatte. Nach ihrer Einreise in die Schweiz im Juli 2007 verweigerte Y._ allerdings die DNA-Analyse und ersuchte stattdessen um Bewilligung des Aufenthalts in der Schweiz für die Dauer des Bewilligungsverfahrens. Die Migrationsbehörden befragten sodann die erste Ehefrau X._s und holten Abklärungen zu dessen wirtschaftlicher Lage sowie zum Bezug von Sozialhilfe ein. C. Mit Verfügung vom 27. Februar 2012 widerrief die Abteilung Migration des Departements des Innern des Kantons Solothurn die Niederlassungsbewilligung X._s, verweigerte die Niederlassungsbewilligung für den Sohn C._ und trat auf das Familiennachzugsgesuch nicht ein. Eine Beschwerde gegen diesen Entscheid wies das Verwaltungsgericht des Kantons Solothurn am 25. September 2012 ab. D. X._ (Beschwerdeführer) führt am 30. Oktober 2012 gegen diesen Entscheid Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt, es sei das Urteil des Verwaltungsgerichts (Vorinstanz) aufzuheben und festzustellen, dass er weiterhin Inhaber einer Niederlassungsbewilligung sei; sodann sei seinem Sohn die Niederlassungsbewilligung zu erteilen und seiner Frau sowie deren beiden Töchtern der Familiennachzug zu gewähren. Eventualiter sei die Streitsache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Ausserdem beantragt er die unentgeltliche Rechtspflege. Zur Begründung führt der Beschwerdeführer aus, die Vorinstanz habe zwar aufgrund verschiedener Indizien eine Scheinehe bejaht. Sie habe dann aber ausgeführt, (auch) für den Bestand der Niederlassungsbewilligung sei von entscheidender Bedeutung, ob er mit seiner heutigen Frau bereits früher eine eheähnliche Beziehung geführt habe. Demnach habe die Vorinstanz die DNA-Analyse als entscheidendes Kriterium gewertet. Es erscheine aber willkürlich, ihm die Bewilligung nicht zu verlängern, weil seine Ehefrau in einem andern Verfahren - demjenigen betreffend den Familiennachzug - die DNA-Analyse verweigere. E. Das Bundesamt für Migration beantragt die Abweisung der Beschwerde, die Vorinstanz sowie die verfügende Behörde beantragen deren Abweisung, soweit darauf einzutreten sei. Mit Verfügung vom 13. November 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zuerkannt. 