Sachverhalt:
A.
Der 1969 geborene A._ bezog für die Zeit vom 1. Juni 1998 bis 1. Oktober 2011 bei einem Invaliditätsgrad von 71 % eine ganze Rente der Invalidenversicherung. Die damalige Rentenaufhebung wurde vom Bundesgericht mit Urteil 8C_113/2013 vom 2. Mai 2013 letztinstanzlich bestätigt.
Nachdem die IV-Stelle des Kantons Graubünden mit Verfügung vom 21. Januar 2015 auf eine erste Neuanmeldung des Versicherten nicht eingetreten war, machte dieser am 25. Juni 2015 erneut eine Verschlechterung seines Gesundheitszustandes geltend. Die IV-Stelle trat nunmehr auf die Neuanmeldung ein und tätigte medizinische Abklärungen; insbesondere holte sie beim Ärztlichen Begutachtungsinstitut (ABI), Basel, eine polydisziplinäre Expertise ein (Gutachten vom 3. Juli 2017; ergänzende Stellungnahme vom 27. Februar 2018). Mit Verfügung vom 8. März 2018 lehnte die IV-Stelle das Neuanmeldegesuch bei einem Invaliditätsgrad von 32 % ab.
B.
Die von A._ hiegegen erhobene Beschwerde hiess das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 19. März 2019 (teilweise) gut und sprach dem Versicherten ab 1. Dezember 2015 eine Viertelsrente der Invalidenversicherung zu, da der Invaliditätsgrad mindestens 42 % und höchstens 49 % betrage.
C.
Mit Beschwerde beantragt A._, ihm sei unter Aufhebung des kantonalen Entscheides ab 1. Dezember 2015 eine ganze Rente der Invalidenversicherung zuzusprechen.
Während die IV-Stelle auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Die Voraussetzungen der Beschwerde in öffentlich-rechtlichen Angelegenheiten sind grundsätzlich gegeben (Art. 82 lit. a, Art. 83 e contrario, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 89 Abs. 1, Art. 90 und Art. 100 Abs. 1 BGG).
1.2. Das Bundesgericht prüft das Bundesrecht von Amtes wegen (Art. 106 Abs. 1 BGG; <ref-ruling> E. 2.3 S. 23 f.) und mit uneingeschränkter (voller) Kognition (Art. 95 lit. a BGG; <ref-ruling> E. 2 S. 236). 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 sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Pflicht zur Begründung 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 (<ref-ruling> E. 1 S. 236 mit Hinweisen).
1.3. Das Bundesgericht kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (Art. 97 Abs. 1 BGG).
Die beschwerdeführende Partei, welche die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substanziiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss Art. 105 Abs. 2 BGG gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen).
2.
Streitig und zu prüfen ist, ob die Vorinstanz Bundesrecht verletzt hat, als sie dem Versicherten keine höhere als eine Viertelsrente der Invalidenversicherung zusprach.
3.
3.1. Der Anspruch auf Leistungen der Invalidenversicherung setzt unter anderem voraus, dass die versicherte Person invalid oder von Invalidität unmittelbar bedroht ist. Invalidität ist gemäss Art. 8 Abs. 1 ATSG die voraussichtlich bleibende oder längere Zeit dauernde ganze oder teilweise Erwerbsunfähigkeit.
3.2. Die Neuanmeldung wird - wie auch das Gesuch um Leistungsrevision - nur materiell geprüft, wenn die versicherte Person glaubhaft macht, dass sich die tatsächlichen Verhältnisse seit der letzten, rechtskräftigen Entscheidung in einem für den Rentenanspruch erheblichen Mass verändert haben (Art. 87 Abs. 3 in Verbindung mit Abs. 2 IVV; <ref-ruling> E. 2.2 S. 72 mit Hinweisen). Gelingt ihr dies nicht, so wird auf das Gesuch nicht eingetreten. Ist die anspruchserhebliche Änderung glaubhaft gemacht, ist die Verwaltung verpflichtet, auf das neue Leistungsbegehren einzutreten und es in tatsächlicher und rechtlicher Hinsicht umfassend zu prüfen (SVR 2014 IV Nr. 33 S. 121, 8C_746/2013 E. 2); sie hat demnach in analoger Weise wie bei einem Revisionsfall nach Art. 17 ATSG vorzugehen (vgl. dazu <ref-ruling>). Stellt sie fest, dass der Invaliditätsgrad oder die Hilflosigkeit seit Erlass der früheren rechtskräftigen Verfügung keine Veränderung erfahren hat, so weist sie das neue Gesuch ab. Andernfalls hat sie zunächst noch zu prüfen, ob die festgestellte Veränderung genügt, um nunmehr eine anspruchsbegründende Invalidität oder Hilflosigkeit zu bejahen, und hernach zu beschliessen.
4.
4.1. Es steht fest und ist letztinstanzlich unbestritten, dass sich der Gesundheitszustand des Versicherten seit der Rentenaufhebung auf Oktober 2011 verschlechtert hat und dieser nunmehr, seit dem 1. Dezember 2015, Anspruch auf eine Rente der Invalidenversicherung hat. Streitig ist demgegenüber der aktuelle Gesundheitszustand und die aus diesem sich ergebenden erwerblichen Einschränkungen des Versicherten. Während die angestammte Tätigkeit als Chauffeur/Bauarbeiter unbestrittenermassen nicht mehr zumutbar ist, stellte das kantonale Gericht in umfassender Würdigung der medizinischen Akten, insbesondere aber gestützt auf das Gutachten des ABI vom 3. Juli 2017 (mit ergänzender Stellungnahme vom 27. Februar 2018), für das Bundesgericht grundsätzlich verbindlich fest, dass der Versicherte in einer angepassten Tätigkeit zu 70 % arbeits- und leistungsfähig wäre. Was der Beschwerdeführer gegen diese Feststellung vorbringt, vermag sie nicht als offensichtlich unrichtig oder als sonstwie bundesrechtswidrig erscheinen zu lassen. Auf ein im Verfahren nach Art. 44 ATSG eingeholtes Gutachten ist rechtsprechungsgemäss abzustellen, wenn nicht konkrete Indizien gegen die Zuverlässigkeit der Expertise sprechen (<ref-ruling> E. 4.4 S. 470). Solche Indizien liegen - wie nachstehende Erwägungen zeigen - entgegen den Vorbringen des Versicherten nicht vor.
4.2. Soweit der Versicherte die Zuverlässigkeit des psychiatrischen Teilgutachtens mit dem Argument in Zweifel zieht, die Dauer des Explorationsgesprächs sei zu kurz gewesen, hat die Vorinstanz zu Recht erwogen, dass es nicht auf die Dauer der Untersuchung ankommt; massgebend ist in erster Linie, ob die Expertise inhaltlich vollständig und im Ergebnis schlüssig ist (vgl. Urteil 8C_356/2018 vom 14. März 2019 E. 4.2 mit weiteren Hinweisen). Dies ist vorliegend entgegen den Ausführungen des Beschwerdeführers zu bejahen. So legte der psychiatrische Experte nachvollziehbar dar, weshalb er unter anderem aufgrund der Aktivitäten des Versicherten eine schwere Depression ausgeschlossen hat. Damit hat der Gutachter auch zum Ausdruck gebracht, dass er diese abweichende Diagnose anderer medizinischer Fachpersonen zur Kenntnis genommen und ernsthaft geprüft, letztlich jedoch verworfen hat. Im Weiteren mag der Versicherte aufgrund der Inkontinenz Scham- und Angstgefühle erleiden; gerade weil diese Beeinträchtigungen jedenfalls bis zu einem gewissen Grad nachvollziehbar sind, erscheint es als einleuchtend, dass sie vom psychiatrischen Experten nicht als Ausdruck einer psychischen Erkrankung gewertet wurden.
4.3. Entgegen den Vorbringen des Beschwerdeführers enthält der Bericht der Dr. med. B._, Fachärztin FMH für Innere Medizin und Rheumatologie, vom 20. November 2017 keine konkreten Indizien, welche gegen die Schlüssigkeit des rheumatologischen Gutachtens sprechen. Soweit ihre Diagnosen von denen des Gutachters vordergründig abweichen, ergibt sich bei näherer Betrachtung, dass der Gutachter die sehr präzisen und ausführlichen Diagnosen der behandelnden Rheumatologin zu einem polytopen Schmerzsyndrom des Bewegungsapparates zusammenfasst. Daraus kann jedoch nicht abgeleitet werden, der Gutachter hätte ein wesentliches von der behandelnden Rheumatologin diagnostiziertes Leiden übersehen. Soweit die Rheumatologin weiter die Schätzung der Arbeitsfähigkeit durch die Gutachter in Zweifel zieht, begründet sie dies nicht mit rheumatologischen Leiden, sondern in erster Linie mit den Darmproblemen und dem depressiven Zustandsbild. Solche Äusserungen jenseits der Grenzen ihres Fachgebietes vermögen aber die gutachterlichen Einschätzungen nicht in Zweifel zu ziehen. Weiter ging auch der rheumatologische Gutachter von einem zervikospondylogenen und lumbospondylogenen Syndrom aus, und hat somit die Rückenproblematik in seine Beurteilung miteinbezogen. Nicht nachzuvollziehen sind schliesslich die Ausführungen des Versicherten, weshalb "die vom Gutachter festgestellte 20%ige Arbeitsunfähigkeit in keinem rechtlich zulässigen Verhältnis zu den von ihm getätigten Feststellungen" sein sollten.
4.4. Auch hinsichtlich seiner Rügen zum gastroenterologischen Teilgutachten vermag der Versicherte nicht durchzudringen: Hinsichtlich der Dauer des Explorationsgespräches gilt das zum psychiatrischen Teilgutachten Ausgeführte (vgl. E. 4.2 hievor); zudem ist zu beachten, dass die gastroenterologischen Diagnosen unter den beteiligten Fachpersonen unbestritten sind. Nachvollziehbar ist auch, dass trotz der Inkontinenz Tätigkeiten, bei denen der Versicherte jederzeit eine Toilette aufsuchen kann, grundsätzlich zumutbar bleiben. Im Weiteren waren die nächtlichen Stuhlgänge dem Experten bekannt, so dass sie keinen Grund darstellen, die Schlüssigkeit und Vollständigkeit seiner Einschätzungen in Zweifel zu ziehen.
4.5. Wie der Beschwerdeführer selber einräumt, haben die Gutachter deutlich zum Ausdruck gebracht, dass sich die Arbeitsunfähigkeiten der einzelnen Fachgebiete ihres Erachtens nur geringfügig kumulieren und dass von einer Arbeits- und Leistungsfähigkeit von 70 % (bei vollzeitlicher Anwesenheit am Arbeitsplatz und erhöhtem Pausenbedarf) auszugehen ist. Nicht nachvollziehbar ist demgemäss, wenn der Beschwerdeführer geltend macht, die gesamte Arbeitsfähigkeit würde auch aus Sicht der ABI-Gutachter erheblich weniger als 70 % ausmachen. Das Abstellen der Vorinstanz auf die von den Gutachtern festgestellte Arbeits- und Leistungsfähigkeit von 70 % erweist sich demnach als nicht bundesrechtswidrig. Damit ist die Beschwerde des Versicherten bei ansonsten unbestritten gebliebener Invaliditätsbemessung abzuweisen.
5.
Dem Verfahrensausgang entsprechend sind die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 Satz 1 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Graubünden und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 25. September 2019
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Der Gerichtsschreiber: Nabold