Sachverhalt: A. Die Ehegatten A.A._ und B.A._ (Beklagte, Beschwerdeführer) führten in den Jahren 2004-2007 ein Verfahren gegen die Obwaldner Steuerbehörden mit einem Streitwert von Fr. 10'773.--. In diesem Verfahren, das durch das Bundesgericht rechtskräftig entschieden wurde, wurden sie ab dem 27. Oktober 2004 durch Rechtsanwalt C._ (Kläger, Beschwerdegegner) vertreten. Dieser stellte wiederholt Rechnung für seine Aufwendungen, wovon nur ein Teil beglichen wurde. B. Mit Klage vom 10. November 2011 beim Kantonsgericht des Kantons Obwalden beantragte der Kläger, die Beklagten seien zu verpflichten, ihm Fr. 38'722.-- nebst Zins zu bezahlen, eventualiter sei ihm in den Betreibungen Nr. 20100957 über Fr. 10'167.35 nebst Zins und Nr. 2015201 über Fr. 877.35 nebst Zins die Rechtsöffnung zu erteilen. Das Kantonsgericht hiess mit Entscheid vom 29. Juni 2015 die Klage teilweise gut und verpflichtete die Beklagten, dem Kläger in solidarischer Haftung Fr. 14'852.05 nebst Zins von 5 % seit 16. März 2010 zu bezahlen. Mit Entscheid vom 10. Mai 2016 hob das Obergericht des Kantons Obwalden den Entscheid des Kantonsgerichts auf, wies die von den Beklagten erhobene Berufung ab und schützte die Anschlussberufung des Klägers. Es hiess die Klage gut und verpflichtete die Beklagten in solidarischer Haftbarkeit, dem Kläger Fr. 38'722.-- nebst Zins zu 5 % seit 16. März 2010 zu bezahlen. Die Kosten des erst- und zweitinstanzlichen Verfahrens auferlegte es den Beklagten und verpflichtete diese in solidarischer Haftbarkeit, dem Kläger für das erstinstanzliche Verfahren eine Parteientschädigung von Fr. 2'500.-- und für das Verfahren vor Obergericht eine solche von Fr. 8'640.-- (inkl. MwSt) zu bezahlen. C. Mit Beschwerde in Zivilsachen beantragen die Beklagten dem Bundesgericht die Aufhebung des angefochtenen Entscheids und die kostenfällige Abweisung der Klage. Der Kläger trägt auf kostenfällige Abweisung der Beschwerde an. Auch das Obergericht beantragt deren Abweisung, soweit darauf einzutreten ist. Die Parteien haben unaufgefordert repliziert und dupliziert. Mit Präsidialverfügung vom 9. August 2016 wurde der Beschwerde die aufschiebende Wirkung erteilt.