Sachverhalt: A. X._ (Kläger; Beschwerdeführer) war seit dem 1. April 2008 bei der Y._ AG (Beklagte; Beschwerdegegnerin) angestellt. Ende Januar 2010 wurde der Kläger, nachdem er aus den Ferien zurückgekommen war, mit einem neuen Arbeitsvertrag (Arbeitsstunden und Lohnreduktion) konfrontiert. Damit wollte die Beklagte die Verträge mit ihren Angestellten rückwirkend per 1. Januar 2010 an den Landesgesamtarbeitsvertrag (LGAV) für das schweizerische Schlosser-, Metallbau-, Landmaschinen-, Schmiede- und Stahlbaugewerbe vom 1. Januar 2006 anpassen. Nachdem sich der Kläger geweigert hatte, den neuen Vertrag zu unterzeichnen, kündigte die Beklagte dem Kläger am 27. Februar 2010 unter Einhaltung der zweimonatigen Kündigungsfrist auf den 30. April 2010, beziehungsweise, zufolge Zugangs der Kündigung erst per 1. März 2010, auf den 31. Mai 2010. B. Am 7. Juni 2010 reichte der Kläger beim Landgericht Uri Klage ein und verlangte Fr. 43'856.60. Diesen Betrag reduzierte er im Verlaufe des Verfahrens auf Fr. 36'776.48 nebst Zins. B.a. Das Landgericht Uri hiess die Klage am 28. Juni 2011 im Umfang von Fr. 4'018.10 nebst Zins gut, wobei die darauf entfallenden Sozialbeiträge zuzüglich der Arbeitgeberbeiträge den entsprechenden Behörden einzuzahlen waren. B.b. Der Kläger legte Berufung ein. In einem ersten Entscheid vom 2. Februar 2012 erkannte das Obergericht des Kantons Uri, mit einer Änderungskündigung dürfe der Arbeitgeber keine Änderung verlangen, die noch vor Ablauf der Kündigungszeit in Kraft treten solle. Mit Blick darauf erachtete es die Kündigung als missbräuchlich. Es wies die Sache zur Festsetzung der Entschädigung nach Art. 336a OR an das Landgericht zurück mit der Massgabe, die weiteren Forderungen des Klägers aus dem Arbeitsvertrag (nunmehr im Lichte des Vorliegens einer missbräuchlichen Kündigung) unter Würdigung aller Umstände materiell zu prüfen. B.c. Am 30. August 2012 setzte das Landgericht die Pönalentschädigung auf Fr. 2'350.-- (entsprechend einem halben Bruttomonatslohn) nebst Zins fest und hielt im Übrigen an seinem Entscheid vom 28. Juni 2011 fest. Dem Umstand, dass das Obergericht die Kündigung als missbräuchlich angesehen hatte, mass das Landgericht für die übrigen Forderungen des Klägers betreffend Lohnzahlung, Überstunden- und Überzeitentschädigung sowie Nachtarbeitsentschädigung keine Bedeutung zu. Das Obergericht habe die diesbezüglichen Erwägungen des Entscheids vom 28. Juni 2011 nicht beurteilt. Daher sah das Landgericht keine Veranlassung, die ursprüngliche Beurteilung zu ändern, und es übernahm die entsprechenden Erwägungen in seinen neuen Entscheid. B.d. Der Kläger legte erneut Berufung ein, worauf die Beklagte Anschlussberufung erhob. Sie bestritt darin gestützt auf ein Rechtsgutachten, das den Rückweisungsentscheid kritisiert, die Missbräuchlichkeit der Kündigung. Am 5. Juli 2013 wies das Obergericht sowohl die Berufung als auch die Anschlussberufung unter Verweis auf den erstinstanzlichen Entscheid ab. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht im Wesentlichen, den Entscheid des Obergerichts vom 5. Juli 2013 aufzuheben und die Beschwerdegegnerin zu verpflichten, ihm Fr. 36'776.48 brutto " inkl. 5% seit den jeweiligen Fälligkeiten " zu bezahlen. Sowohl die Vorinstanz als auch die Beschwerdegegnerin haben auf Vernehmlassung verzichtet.