Sachverhalt: A. Der Erschliessungsplan der Gemeinde Feusisberg sieht die Erstellung einer Groberschliessungsstrasse für eine im Gebiet Rahmensbüel gelegene Ein- und Zweifamilienhauszone vor. Gemäss Art. 13 des Reglements zum Erschliessungsplan beträgt der Kostenanteil der Gemeinde 10 %. Am 28. August 2008 erteilte der Gemeinderat Feusisberg die Baubewilligung für das Strassenbauprojekt. Dagegen beschritt unter anderem X._ den Rechtsweg. Seine Beschwerde wurde in letzter Instanz vom Bundesgericht abgewiesen (Urteil 1C_475/2009 vom 16. März 2010). Der zum Strassenbauprojekt gehörende Beitragsplan "Erschliessung Rahmensbüel, Schindellegi" vom 21. Juni 2010 wurde vom 25. Juni bis zum 15. Juli 2010 öffentlich aufgelegt. Mit Beschluss vom 7. Dezember 2010 wies der Gemeinderat eine von X._ erhobene Einsprache ab und genehmigte den Beitragsplan. X._ erhob dagegen Beschwerde beim Regierungsrat des Kantons Schwyz, der das Rechtsmittel indessen am 21. Juni 2011 abwies. In der Folge gelangte X._ mit Beschwerde ans Verwaltungsgericht. Dieses wies das Rechtsmittel mit Entscheid vom 23. November 2011 ebenfalls ab. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 1. Februar 2012 beantragen X._, Y._, Z._ und W._, der Entscheid des Verwaltungsgerichts sei aufzuheben und die Sache sei zum neuen Entscheid an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht hat auf eine Vernehmlassung verzichtet. Der Regierungsrat beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Gemeinderat beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Die Beschwerdeführer halten in ihrer Stellungnahme dazu an ihren Anträgen und Rechtsauffassungen fest. Der Regierungsrat und der Gemeinderat haben in der Folge eine weitere Eingabe eingereicht.