Sachverhalt: A. A.a Der 1959 geborene T._ arbeitete seit dem 18. März 1991 als Zustellbeamte bei der Post. Ab dem 22. September 1997 verrichtete er Schonarbeit im Innendienst. Im April 1999 meldete er sich bei der Invalidenversicherung zum Leistungsbezug an. Nach verschiedenen Abklärungen sprach ihm die IV-Stelle des Kantons Basel-Stadt mit Verfügung vom 8. Mai 2006 ab 1. August 1998 eine halbe Rente, ab 1. Januar 2004 eine Dreiviertelsrente und ab 1. Oktober 2005 eine ganze Rente zu. A.b Im Dezember 2008 leitete die IV-Stelle ein Revisionsverfahren ein und teilte T._ in der Mitteilung vom 25. Februar 2009 zunächst mit, er habe Anspruch auf die bisherige Invalidenrente. In der Folge liess sie ihn allerdings im Medizinischen Zentrum O._ begutachten (Gutachten vom 21. März 2010) und verneinte mit Verfügung vom 17. August 2010 bei einem Invaliditätsgrad von 28 % einen weiteren Rentenanspruch. B. Die hiegegen eingereichte Beschwerde wies das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 29. Juni 2011 ab. C. Mit Beschwerde lässt T._ die Aufhebung des vorinstanzlichen Entscheides und weiterhin die Ausrichtung einer ganzen Rente der Invalidenversicherung beantragen. Eventualiter sei die Sache zum neuen Entscheid an die Vorinstanz zurückzuweisen. Ferner wird um unentgeltliche Prozessführung und Verbeiständung ersucht. D. Mit Verfügung vom 16. November 2011 stellte die Instruktionsrichterin T._ in Aussicht, die Beschwerde mit der substituierten Begründung der Wiedererwägung der ursprünglichen Rentenverfügung vom 8. Mai 2006 abzuweisen. Diese rechtliche Begründung wurde im Verfahren bisher nicht erwähnt. T._ wurde die Möglichkeit gegeben, sich hierzu zu äussern. Mit Eingabe vom 11. Januar 2012 nahm er dazu Stellung. 