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.