Sachverhalt:
A. A.a Der 1964 geborene B._ war vom 1. März 1995 bis 30. November 1996 in der Produktion der Firma D._ AG tätig. Am 7. April 1997 meldete er sich unter Hinweis auf eine Allergie bei der IV-Stelle Solothurn zum Leistungsbezug an und beantragte die Umschulung auf eine neue Tätigkeit. Nach Beizug der Akten der Schweizerischen Unfallversicherungsanstalt (SUVA) und nach Durchführung des Vorbescheidverfahrens wies die IV-Stelle Solothurn das Leistungsbegehren mit Verfügung vom 10. Februar 1999 ab; der Versicherte erhob gegen diese Verfügung keine Beschwerde.
A.b Am 20. Januar 2003 meldete sich B._ erneut bei der IV-Stelle Solothurn zum Leistungsbezug an. Mit Verfügung vom 18. April 2003 verneinte die IV-Stelle einen Anspruch auf berufliche Eingliederungsmassnahmen. Dagegen erhob der Versicherte Einsprache und beantragte eventuell die direkte Zusprache einer ganzen Invalidenrente. Mit Einspracheentscheid vom 30. November 2004 anerkannte die IV-Stelle einen Anspruch des Versicherten auf Arbeitsvermittlung; im Übrigen wies sie das Leistungsbegehren bei einem Invaliditätsgrad von 28 % ab. Die von B._ hiegegen erhobene Beschwerde hiess das Versicherungsgericht des Kantons Solothurn mit Entscheid vom 21. November 2005 teilweise gut, hob den Einspracheentscheid insoweit ein über die Arbeitsvermittlung hinausgehender Leistungsanspruch verneint wurde auf und wies die Sache zu ergänzenden Abklärungen an die IV-Stelle Solothurn zurück.
A.c Nachdem die IV-Stelle Solothurn die vom kantonalen Gericht geforderten Abklärungen getätigt hatte, wies sie das Leistungsbegehren des Versicherten - soweit die Ausrichtung einer IV-Rente betreffend - nach Durchführung des Vorbescheidverfahrens mit Verfügung vom 8. Januar 2008 bei einem Invaliditätsgrad von 31 % erneut ab.
B. Die von B._ hiegegen erhobene Beschwerde wies das Versicherungsgericht des Kantons Solothurn mit Entscheid vom 26. März 2009 ab.
C. Mit Beschwerde beantragt B._, ihm sei unter Aufhebung der Verfügung und des kantonalen Gerichtsentscheides mindestens eine Viertelsrente zuzusprechen und ihm sei der erhobene Kostenvorschuss zurückzuerstatten.
Während die IV-Stelle Solothurn auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 1.4.1 S. 254).
1.2 Da der vorinstanzliche Entscheid nicht Geldleistungen der Unfall- oder der Militärversicherung betrifft, prüft das Bundesgericht nur, ob das vorinstanzliche Gericht Bundesrecht verletzte, einschliesslich Überschreitung oder Missbrauch des Ermessens oder ob der rechtserhebliche Sachverhalt offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt wurde.
2. Streitig und zu prüfen ist, ob die Vorinstanz Bundesrecht verletzte, indem sie die rentenablehnende Verfügung der Beschwerdegegnerin geschützt hat.
3. Wie das kantonale Gericht zutreffend erwogen hat, bedarf die Zusprechung einer Invalidenrente aufgrund einer Neuanmeldung, analog zur Rentenrevision (<ref-law>), einer anspruchsrelevanten Änderung des Invaliditätsgrades. Dabei bildet die letzte, auf einer materiellen Prüfung des Rentenanspruchs beruhende, rechtskräftige Verfügung den Ausgangspunkt und die streitige Verfügung den Endpunkt für die Beurteilung, ob eine solche Änderung eingetreten ist (<ref-ruling>; Urteil 8C_776/2008 vom 18. Juni 2009 E. 2).
4. 4.1 Die Vorinstanz hat in Würdigung der gesamten medizinischen Akten für das Bundesgericht grundsätzlich verbindlich festgestellt, dass sich der Gesundheitszustand des Beschwerdeführers in der Zeit zwischen der Verfügung vom 10. Februar 1999 und der hier streitigen Verfügung vom 8. Januar 2008 nicht wesentlich geändert hat. Daraus schloss sie ohne weiteres auf Abweisung der Beschwerde; das kantonale Gericht wertete somit die Anmeldung vom 28. Januar 2003 als Neuanmeldung nach rechtskräftiger Ablehnung eines Rentenanspruchs.
4.2 Gemäss ihrem Wortlaut bezieht sich die Verfügung vom 10. Februar 1999 auf berufliche Massnahmen in Form einer Umschulung. Zwar wurde im Dispositiv pauschal das "Leistungsbegehren" abgewiesen; der Versicherte hatte indessen bis im Februar 1999 noch keine anderen Leistungen als eine Umschulung beantragt. Ein allfälliger Rentenanspruch wurde von der IV-Stelle nicht geprüft, er bildete somit auch nicht Gegenstand jener Verfügung. Bezieht sich die Verfügung vom 10. Februar 1999 nicht auf einen Rentenanspruch, so war ein solcher im Zeitpunkt der zweiten Anmeldung im Jahre 2003 noch nicht rechtskräftig abgelehnt. Die Vorinstanz hat somit gegen Bundesrecht verstossen, indem sie die Anmeldung vom 28. Januar 2003 lediglich als Neuanmeldung nach rechtskräftiger Ablehnung eines Rentenanspruchs betrachtete und ihre Prüfung zwar folgerichtig, aber nach dem Gesagten zu Unrecht, auf die Frage beschränkte, ob sich der Gesundheitszustand zwischen dem 10. Februar 1999 und dem 8. Januar 2008 wesentlich verändert habe.
4.3 Demnach ist der vorinstanzliche Entscheid vom 26. März 2009 aufzuheben und die Sache ist an das kantonale Gericht zurückzuweisen, damit dieses - wie vor ihr die IV-Stelle in ihrer Verfügung vom 8. Januar 2008 an sich zutreffenderweise, aber gegen den für die IV-Stelle und die Vorinstanz im zweiten Verfahren verbindlichen (vgl. <ref-ruling> E. 5.2.3 S. 484) Entscheid des kantonalen Gerichts vom 21. November 2005 verstossend - die Anmeldung vom 28. Januar 2003 als erstmaligen Antrag auf eine IV-Rente behandle und entsprechend über die Beschwerde neu entscheide.
5. Der Beschwerdeführer rügt, es bestehe im Kanton Solothurn keine genügende gesetzliche Grundlage für die Erhebung eines Kostenvorschusses bzw. für die Auferlegung von Gerichtskosten in einem IV-Verfahren. Soweit die Auferlegung von Gerichtskosten betreffend, ist die Rüge mit vorliegender Aufhebung des kantonalen Entscheides gegenstandslos geworden. Durch die Erhebung eines Kostenvorschusses erleidet - da der Kostenvorschuss geleistet wurde - der Beschwerdeführer ohnehin keinen nicht wieder gutzumachenden Nachteil (<ref-law>), so dass auf die diesbezügliche Rüge zum jetzigen Zeitpunkt nicht einzutreten ist.
6. Die Gerichtskosten für das bundesgerichtliche Verfahren werden der Beschwerdegegnerin auferlegt (<ref-law>). Der Beschwerdeführer hat für das bundesgerichtliche Verfahren Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird, soweit auf sie einzutreten ist, gutgeheissen und der Entscheid des Versicherungsgerichts des Kantons Solothurn vom 26. März 2009 aufgehoben. Die Sache wird an die Vorinstanz zurückgewiesen, damit sie im Sinne der Erwägungen verfahre und über die Beschwerde gegen die Verfügung vom 8. Januar 2008 neu entscheide.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Solothurn, der Ausgleichskasse des Kantons Solothurn und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 11. September 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Holzer