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.

Erwägungen:
1. 1.1 Die vorliegende Beschwerde richtet sich gegen einen letztinstanzlichen kantonalen Entscheid, mit welchem die Beschwerdeführer verpflichtet werden, Schadenersatz für entgangene Beiträge gestützt auf das (bis 31. Dezember 2008 in Kraft gewesene) kantonale Gesetz vom 8. Juni 1958 über Kinderzulagen für Arbeitnehmer (KZG/ZH; 836.1) zu leisten. Die Beschwerdeführer rügen, es bestehe keine gesetzliche Grundlage für die Geltendmachung dieses Schadenersatzes, und berufen sich dabei auf die Anforderungen von <ref-law> sowie den dazu ergangenen <ref-ruling>.
1.2 Nach <ref-law> überprüft das Bundesgericht die Anwendung kantonalen Rechts nur daraufhin, ob sie zu einer Bundesrechtsverletzung führt, wozu namentlich die willkürliche Rechtsanwendung gehört. Frei überprüft das Bundesgericht hingegen, ob das willkürfrei ausgelegte kantonale Recht dem Bundesrecht widerspricht. Zum frei überprüfbaren Bundesrecht in diesem Sinne gehört auch das Legalitätsprinzip im Abgaberecht, welches verlangt, dass öffentlich-rechtliche Geldleistungen nur mit einer hinreichend bestimmten gesetzlichen Grundlage erhoben werden dürfen (<ref-law>; <ref-ruling> E. 6.1 S. 180).
2. In seinem Urteil 9C_720/2008 vom 7. Dezember 2009 äusserte sich das Bundesgericht in E. 5 zur Frage, ob § 33 Abs. 2 KZG/ZH (in der hier massgeblichen bis 31. Dezember 2007 gültig gewesenen Fassung) eine genügende gesetzliche Grundlage sei zur Erhebung von Schadenersatz im Rahmen eines Verfahrens nach <ref-law>, und bejahte dies in Bestätigung des Urteils 2P.251/1996 vom 30. Juni 1997. Die Rechtsprechung lege keinen strengen Massstab an die Bestimmtheit der verweisenden Norm an. Dies sei etwa am Beispiel der entgangenen Beiträge an die Arbeitslosenversicherung ersichtlich, welche gemäss <ref-ruling> von <ref-law> miterfasst würden, obwohl der massgebliche <ref-law> seit jeher nur in allgemeiner Weise vorschreibe, dass "für den Bereich der Beiträge die AHV-Gesetzgebung sinngemäss" gelte, soweit das AVIG nichts anderes bestimme. Zudem sei mit Art. 25 lit. c des auf den 1. Januar 2009 in Kraft getretenen Bundesgesetzes vom 24. März 2006 über die Familienzulagen (FamZG; SR 836.2) eine bundesrechtliche Gesetzesgrundlage geschaffen worden, welche hinsichtlich der Arbeitgeberhaftung für entgangene Sozialversicherungsbeiträge ausdrücklich auf <ref-law> verweise. Aus Gleichbehandlungs- und Praktikabilitätsüberlegungen sei es geboten, die noch kleine Zahl von Fällen unter bisherigem Recht im Ergebnis nicht anders zu behandeln als die grosse Zahl der übrigen. Die <ref-ruling> zugrunde liegende kantonalzugerische Norm sei keine hinreichende gesetzliche Grundlage, da sie nicht direkt auf das AHVG verweise, sondern eine problematischere indirekte Verweisung sei. Abschliessend hielt das Bundesgericht fest, auch unter dem Blickwinkel der - gegenüber dem Urteil 2P.251/1996 - nunmehr uneingeschränkten Überprüfungsbefugnis (vgl. E. 1.2) bilde § 33 Abs. 2 KZG/ZH eine hinreichende gesetzliche Grundlage für die Erhebung von Schadenersatz für entgangene Sozialversicherungsbeiträge nach kantonalem Recht.
3. Es besteht kein Anlass, von dieser Rechtsprechung abzuweichen. Die Einwände der Beschwerdeführer bezüglich der hinreichenden gesetzlichen Grundlage im Sinne von <ref-law> (fehlender ausdrücklicher Verweis auf <ref-law> im kantonalen Recht, Problematik der dynamischen Verweisung) wurden bereits im erwähnten Urteil einlässlich geprüft und verworfen. Daran ändert auch die Berufung auf <ref-ruling> nichts. Das Bundesgericht hat einlässlich begründet, weshalb daraus nichts zur Rechtslage im Kanton Zürich abgeleitet werden kann. Auch aus dem zutreffenden Hinweis, dass vorliegend die Schadenersatzpflicht für die kantonal geschuldeten Beiträge gegenüber jenen nach Bundesrecht - anders als im Urteil 2P.251/1996 festgehalten - quantitativ nicht von untergeordneter Bedeutung ist, ergibt sich bezüglich der hier strittigen Rechtslage nichts zu Gunsten der Beschwerdeführer. Was den Verweis auf den Entscheid des Versicherungsgerichts des Kantons Aargau betrifft (AHI 1998 S. 138), hat sich das Bundesgericht auch dazu bereits im Urteil 9C_720/2008 geäussert. Schliesslich verletzt die Haftung für Schadenersatz infolge entgangener Beiträge an die (Familien-)Ausgleichskasse auch nicht die Eigentumsgarantie von <ref-law>, da die Voraussetzungen gemäss <ref-law> (gesetzliche Grundlage, öffentliches Interesse, Verhältnismässigkeit und Respektierung des Kerngehalts) gegeben sind. Darüber hinausgehende Rügen, etwa bezüglich der konkreten Schadenshöhe oder dem ihnen vorgeworfenen Verschulden, werden von den Beschwerdeführern nicht erhoben, so dass es beim vorinstanzlichen Entscheid sein Bewenden hat.
4. Das Gesuch um Erteilung der aufschiebenden Wirkung wird mit dem Entscheid in der Hauptsache gegenstandslos (vgl. Urteil 8C_479/2007 vom 4. Januar 2008, E. 4 mit Hinweis).
5. Das Verfahren ist kostenpflichtig. Die unterliegenden Beschwerdeführer tragen die Gerichtskosten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 1'400.- werden den Beschwerdeführern auferlegt.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 27. Januar 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Riedi Hunold