Sachverhalt: A. Mit Einspracheentscheid vom 3. Mai 2012 verpflichtete die Ausgleichskasse des Kantons Zürich A.A._ und B.A._, ihr in solidarischer Haftung Schadenersatz im Betrag von Fr. 73'157.60 für entgangene Sozialversicherungsbeiträge zu entrichten. Die vom 4. Mai 2012 datierende Sendung (Poststempel), adressiert an Rechtsanwalt C._, der A.A._ und B.A._ seit dem 23. Juli 2007 in dieser Sache vertreten hatte, wurde mit dem Vermerk "weggezogen, Nachsendefrist abgelaufen" retourniert. In der Folge verschickte die Ausgleichskasse den Entscheid direkt an A.A._ und B.A._, welcher mit dem Hinweis auf bis ca. 31. August dauernde Ferienabwesenheit wiederum retourniert wurde. Am 30. August 2012 sandte die Ausgleichskasse den Einspracheentscheid A.A._ und B.A._ erneut eingeschrieben zu unter Hinweis auf die erfolglosen Zustellversuche. B. Auf eine dagegen erhobene Beschwerde trat das Sozialversicherungsgericht des Kantons Zürich mit Beschluss vom 22. Dezember 2012 nicht ein. In Gutheissung der hiegegen erhobenen Beschwerde hob das Bundesgericht mit Urteil 9C_214/2013 vom 31. August 2013 den angefochtenen Entscheid auf und wies die Sache zur Gewährung des Replikrechts und zur Neubeurteilung an die Vorinstanz zurück. C. Das Sozialversicherungsgericht des Kantons Zürich führte einen zweiten Schriftenwechsel durch und trat mit Beschluss vom 31. August 2015 wiederum nicht auf die Beschwerde ein. D. A.A._ und B.A._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, der angefochtene Beschluss sei aufzuheben und die Sache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem sei der Beschwerde die aufschiebende Wirkung zu erteilen. Während die Beschwerdegegnerin auf Abweisung der Beschwerde schliesst, lässt sich das Bundesamt für Sozialversicherungen nicht vernehmen.