Sachverhalt: A. A.a R._, geboren 1957, war als Bauhilfsarbeiter tätig. Am 16. April 2002 meldete er sich bei der Invalidenversicherung zum Leistungsbezug an. Nach Abklärung des medizinischen Sachverhalts (u.a. mittels MEDAS-Gutachten vom 14. Juli 2005) sowie der beruflich-erwerblichen Verhältnisse sprach die IV-Stelle Luzern R._ mit Verfügung vom 3. März 2006 rückwirkend ab 1. Oktober 2001 eine ganze Invalidenrente (Invaliditätsgrad von 100 %) und ab 1. August 2002 eine halbe Invalidenrente (Invaliditätsgrad von 58 %) zu. Diese hob sie auf den 31. März 2003 mangels eines rentenbegründenden Invaliditätsgrades auf. Die Verfügung erwuchs unangefochten in Rechtskraft. A.b Am 17. Oktober 2007 meldete sich R._ wegen ausstrahlender starker Rückenschmerzen sowie Nacken- und Kopfschmerzen erneut bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle sprach dem Versicherten eine Verschlechterung des Gesundheitszustandes ab und trat mit Verfügung vom 5. September 2008 auf das Gesuch nicht ein. Die dagegen erhobene Beschwerde hiess das Verwaltungsgerichts des Kantons Luzern mit Entscheid vom 23. März 2010 in dem Sinne gut, dass es die Nichteintretensverfügung aufhob und die Sache zur weiteren Abklärung an die IV-Stelle zurückwies. A.c In der Folge holte die IV-Stelle verschiedene Arztberichte und ein weiteres Gutachten der Medas (vom 25. August 2011) ein. Nach Durchführung des Vorbescheidverfahrens sprach sie R._ mit Verfügung vom 12. März 2012 ab 1. April 2012 eine halbe Invalidenrente zu (Invaliditätsgrad von 59 %). Mit Verfügung vom 11. April 2012 stellte sie ihm die Berechnung des rückwirkenden Rentenanspruchs vom 1. Oktober 2011 bis 31. März 2012 zu. B. Gegen die Verfügungen erhob R._ Beschwerde beim Verwaltungsgericht des Kantons Luzern. Er beantragte die Vereinigung der Verfahren und Zusprache einer Rente nach Gesetz. Mit Entscheid vom 16. August 2012 vereinigte das kantonale Gericht die zwei Verfahren. Auf die Beschwerde gegen die Verfügung vom 11. April 2012 trat es nicht ein. Die Beschwerde gegen die Verfügung vom 12. März 2012 hiess es teilweise gut und legte den Rentenbeginn auf den 1. Juli 2011 fest. Im Übrigen wies es die Beschwerde ab. C. R._ lässt hiegegen Beschwerde in öffentlich-rechtlichen Angelegenheiten führen. Er beantragt, der angefochtene Entscheid sei aufzuheben und es sei ihm (bei einem Invaliditätsgrad von 60 %) eine Rente nach Gesetz zuzusprechen. 