Sachverhalt: A. Die X._ AG war ab 1. April 1998 bei der Ausgleichskasse des Kantons Zürich (nachfolgend: Ausgleichskasse) als Arbeitgeberin angeschlossen. H._ amtete als Verwaltungsrat und A._ war Geschäftsführer der Gesellschaft. Diese verlegte ihren Sitz per ... 2006 in den Kanton Wallis. Am ... 2006 wurde über die X._ AG der Konkurs eröffnet. Die Ausgleichskasse verpflichtete am 13. Juli 2007 H._ und A._ in solidarischer Haftung zur Bezahlung von Fr. 39'167.70 Schadenersatz. Diesen reduzierte sie in ihren Einspracheentscheiden vom 23. Januar 2008 auf Fr. 32'643.80. B. H._ und A._ liessen dagegen Beschwerde erheben. Mit Verfügungen vom 14. und 20. März 2008 trat das Sozialversicherungsgericht des Kantons Zürich auf die beiden Beschwerden nicht ein, soweit sich der ihnen zugrunde liegende Schadenersatz auf Bundesrecht abstützte, überwies die Sache diesbezüglich an das Kantonsgericht Wallis und vereinigte die bei ihm verbleibenden Prozesse. Das Kantonsgericht Wallis wies die Beschwerden mit in Rechtskraft erwachsenem Entscheid vom 12. Mai 2009 ab. Das Sozialversicherungsgericht des Kantons Zürich wies die Beschwerden, soweit sie in seine Zuständigkeit fielen, mit Entscheid vom 21. September 2009 ab. C. H._ und A._ lassen Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Begehren, es seien der vorinstanzliche Entscheid und die Schadenersatzforderung gegen sie aufzuheben. Zusätzlich ersuchen sie um Gewährung der aufschiebenden Wirkung ihrer Beschwerde. Die Ausgleichskasse des Kantons Zürich enthielt sich eines Antrags, schloss sich aber bezüglich des Gesuches um Wiederherstellung der aufschiebenden Wirkung den Beschwerdeführern an. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung. 