Erwägungen:
1. 1.1 Der serbische Staatsangehörige albanischer Volkszugehörigkeit X._ (geb. 1967) war von 1994 bis 1997 in Serbien mit einer Landsfrau verheiratet. Im März 1994 kam die gemeinsame Tochter A._ zur Welt. Im Rahmen der 1997 erfolgten Scheidung wurde das Sorgerecht dem Vater zugeteilt.
X._ reiste am 5. Mai 1997 zum ersten Mal in die Schweiz ein. Nachdem sein Asylgesuch rechtskräftig abgewiesen wurde, galt er seit dem 4. September 1998 als verschwunden. Am 4. Januar 2000 stellte X._ erneut ein Asylgesuch. Er führte dazu aus, er habe sich von September 1998 bis Dezember 1999 in Albanien aufgehalten, da er nicht nach Serbien habe reisen können. Seine Tochter A._ habe bei seinen Eltern in Serbien gewohnt. Nach rechtskräftiger Abweisung des Asylgesuchs galt X._ seit dem 22. August 2001 wieder als verschwunden. Am 10. Dezember 2007 reiste X._ erneut illegal in die Schweiz ein und heiratete am 27. Februar 2008 die in der Schweiz niederlassungsberechtigte serbische Staatsangehörige Y._ (geb. 1969). Mit Verfügung vom 2. Juni 2008 wurde X._ im Rahmen des Familiennachzugs die Aufenthaltsbewilligung erteilt. Im Dezember 2008 kam die gemeinsame Tochter B._ zur Welt.
1.2 Am 31. Dezember 2009 reiste die Tochter aus erster Ehe, A._, in die Schweiz ein. Am 15. Januar 2010 reichte X._ ein Gesuch um Familiennachzug mit dem Zweck "Zusammenleben von Vater und Kind" ein. Nach Gewährung des rechtlichen Gehörs wies die Migrationsbehörde des Kantons Solothurn mit Verfügung vom 11. August 2011 das Gesuch um Familiennachzug ab und ordnete an, A._ habe die Schweiz bis 19. September 2011 zu verlassen. Mit Urteil vom 18. Januar 2012 wies das Verwaltungsgericht des Kantons Solothurn die dagegen erhobene Beschwerde ab und ordnete an, A._ habe die Schweiz bis 29. Februar 2012 zu verlassen.
1.3 Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 27. Februar 2012 beantragt X._, der Familiennachzug von A._ sei zu bewilligen, eventualiter seien die Akten zur Neubeurteilung an die Migrationsbehörde zurückzuweisen.
1.4 Mit Verfügung vom 1. März 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt. Auf die Anordnung eines Schriftenwechsels wurde verzichtet.
2. 2.1 Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts ausgeschlossen, wenn um eine Bewilligung ersucht wird, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
2.2 Der Beschwerdeführer verfügt als Ausländer über eine Aufenthaltsbewilligung, nicht jedoch über eine Niederlassungsbewilligung. Daher kann er sich für den Nachzug seiner Tochter aus erster Ehe nicht auf Art. 43 Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) stützen. Ebenso wenig kommt ein Anspruch nach Art. 43 AuG in Bezug auf seine jetzige Ehefrau, die über die Niederlassungsbewilligung verfügt, in Betracht, denn sie ist nicht die Mutter der Tochter (vgl. zu Stiefkindern bzw. Stiefeltern Urteil 2C_537/2009 vom 31. März 2010 E. 2.2.2). Der Beschwerdeführer kann sich nach dem internen Ausländerrecht somit nur auf Art. 44 AuG stützen, der den Nachzug durch Ausländer mit Aufenthaltsbewilligung regelt. Diese Bestimmung räumt ihm aber, anders als Art. 42 und 43 AuG, keinen Nachzugsanspruch im Sinne von <ref-law> ein (<ref-ruling> E. 1.2 S. 287 mit Hinweisen).
2.3 Auch der Niederlassungs- und Konsularvertrag zwischen der Schweiz und Serbien vom 16. Februar 1888 (SR 0.142.118.181) verschafft keinen Bewilligungsanspruch für die Familienangehörigen (Urteil 2C_205/2011 vom 3. Oktober 2011 E. 1 mit Hinweisen).
2.4 Wie der Beschwerdeführer zu Recht geltend macht, kann er sich für den Nachzug seiner Tochter allerdings auf den Schutz des Familienlebens nach <ref-law> und Art. 8 EMRK berufen. Denn durch das Zusammenleben mit der niedergelassenen Ehefrau hat er selber einen Anspruch auf Verlängerung seiner Aufenthaltsbewilligung gemäss Art. 43 Abs. 1 AuG und damit ein gefestigtes Aufenthaltsrecht. Zudem macht er eine intakte und tatsächlich gelebte Beziehung zu seiner Tochter geltend. Insoweit wäre daher auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> grundsätzlich einzutreten (vgl. <ref-ruling> E. 1.3 S. 287 mit Hinweisen).
Allerdings gilt es hier noch Folgendes zu beachten: Der Beschwerdeführer hat am 15. Januar 2010 ersucht, seine zu diesem Zeitpunkt rund 16-jährige Tochter in die Schweiz nachziehen zu können. Hierauf bestand wie soeben erwähnt kein Anspruch gestützt auf das interne Ausländerrecht. Ein solcher Anspruch ergibt sich heute indessen auch nicht mehr aus <ref-law> bzw. Art. 8 EMRK, da die nachzuziehende Tochter inzwischen (am 26. März 2012) volljährig geworden ist und zwischen ihr und ihrem Vater kein besonderes Abhängigkeitsverhältnis besteht bzw. ein solches nicht substantiiert geltend gemacht worden ist. Anders als in Bezug auf Art. 42 ff. AuG ist gemäss einer konstanten Praxis in Bezug auf <ref-law> bzw. Art. 8 EMRK das Alter im heutigen Zeitpunkt (und nicht das Alter im Zeitpunkt der Einreichung des Gesuchs) massgebend für den Entscheid über den materiell-rechtlichen Anspruch auf Familiennachzug sowie für die Frage der Zulässigkeit der Beschwerde in öffentlich-rechtlichen Angelegenheiten, welche diesen Anspruch voraussetzt (<ref-ruling> E. 3.2 S. 500; <ref-ruling> E. 2 S. 13; <ref-ruling> E. 1f S. 262; Urteile 2C_205/2011 vom 3. Oktober 2011 E. 1; 2C_606/2009 vom 17. März 2010 E. 1). Damit erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten mangels eines Rechtsanspruchs als unzulässig.
3. 3.1 Nachdem der Beschwerdeführer keinen Rechtsanspruch auf den beantragten Familiennachzug hat, fehlt es ihm auch an einem rechtlich geschützten Interesse, um im Rahmen einer subsidiären Verfassungsbeschwerde (<ref-law>) an das Bundesgericht gelangen zu können. Allerdings kann mit diesem Rechtsmittel unabhängig von einem Bewilligungsanspruch eine Verletzung von Parteirechten gerügt werden, deren Missachtung einer formellen Rechtsverweigerung gleichkommt (sog. "Star"-Praxis: <ref-ruling> E. 2 mit Hinweisen).
3.2 Der Beschwerdeführer rügt eine Verletzung des Anspruchs auf rechtliches Gehör: Die im angefochtenen Urteil erwähnte "Einschätzung" des Kantonsarztes vom 1. April 2010 (vgl. angefochtenes Urteil Ziff. 4b) sei dem Beschwerdeführer vor Eröffnung des Urteils nicht bekannt gewesen. Hätte der Beschwerdeführer von diesem Dokument Kenntnis gehabt, so hätte er einen ausführlichen Bericht über den Gesundheitszustand seiner Eltern erwirken können.
Die Vorinstanz hat dazu im angefochtenen Entscheid ausgeführt, es handle sich gemäss "Einschätzung" des Kantonsarztes vom 1. April 2010 bei dem - in einer von einem Gerichtsdolmetscher übersetzten Bestätigung des serbischen Krankenhauses - beschriebenen Leiden des Vaters um einen Herzinfarkt mit Herzinsuffizienz.
3.3 Eine Verletzung des rechtlichen Gehörs des Beschwerdeführers ist hier nicht ersichtlich: Einerseits bildet die von ihm erwähnte "Einschätzung" Bestandteil der Verfahrensakten; er bringt jedoch nicht vor, er habe keine Akteneinsicht nehmen können bzw. die "Einschätzung" habe sich nicht in den Verfahrensakten befunden. Er macht bloss geltend, im Schreiben des Migrationsamtes vom 12. April 2010 sei die "Einschätzung" nicht erwähnt worden; mit diesem Schreiben hat aber die Migrationsbehörde nur festgehalten, die Tochter des Beschwerdeführers müsse den Entscheid im Ausland abwarten. Diesem Schreiben ist kein Gesuch um Akteneinsicht vorausgegangen. Andererseits handelt es sich bei der zitierten "Einschätzung" ohnehin bloss um eine drei Zeilen umfassende Übersetzung von lateinischen Ausdrücken in der Originalbestätigung des serbischen Krankenhauses, welche dem Beschwerdeführer bekannt war, da er sie selber eingereicht hat. Bei diesem Ergebnis kann offen gelassen werden, ob der Gesundheitszustand des Vaters des Beschwerdeführers angesichts anderer Betreuungsmöglichkeiten für die Tochter überhaupt eine entscheidwesentliche Tatsache darstellt.
Im Vorgehen der Vorinstanz kann damit weder eine formelle Rechtsverweigerung noch eine Verletzung des Anspruchs des Beschwerdeführers auf rechtliches Gehör erblickt werden. Somit ist die subsidiäre Verfassungsbeschwerde abzuweisen, soweit darauf eingetreten werden kann.
4. Nach dem Gesagten ist auf die Eingabe als Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht einzutreten. Als subsidiäre Verfassungsbeschwerde ist sie abzuweisen, soweit darauf eingetreten werden kann.
Der unterliegende Beschwerdeführer wird dementsprechend kostenpflichtig (<ref-law>). Es sind keine Parteientschädigungen geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Eingabe wird als Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht eingetreten. Als subsidiäre Verfassungsbeschwerde wird sie abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Departement des Innern des Kantons Solothurn, dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 22. Juni 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger