Sachverhalt:
A. Die Eheleute V._ und W._ reichten am 31. März 2009 ein Baugesuch betreffend die Parzelle Nr. 454 an der Rahmensbüelstrasse 40 in Schindellegi, Gemeinde Feusisberg, ein. Dieses umfasste den Abbruch des bestehenden Gebäudes und den Neubau eines Einfamilienhauses. Das Baugesuch wurde im Amtsblatt vom 9. April 2009 publiziert. Der Gemeinderat Feusisberg wies die dagegen erhobenen Einsprachen mit Beschluss vom 27. August 2009 ab, soweit er darauf eintrat, und erteilte die Baubewilligung.
Während der Bauphase erhoben die Eheleute X._ und Y._, die sich am bisherigen Verfahren nicht beteiligt hatten, eine nachträgliche Einsprache. Diese wurde vom Gemeinderat Feusisberg mit Entscheid vom 1. Juni 2010 abgewiesen. Eine gegen den Entscheid des Gemeinderats eingelegte Verwaltungsbeschwerde wies der Regierungsrat des Kantons Schwyz mit Beschluss vom 22. März 2011 ab. In der Folge gelangten die Eheleute X._ und Y._ mit Beschwerde an das Verwaltungsgericht des Kantons Schwyz. Dieses wies ihr Rechtsmittel mit Entscheid vom 21. September 2011 ebenfalls ab.
B. Mit einer als "Verfassungsbeschwerde" bezeichneten Eingabe an das Bundesgericht vom 7. November 2011 beantragen die Eheleute X._ und Y._, die vorinstanzlichen Entscheide seien aufzuheben und der Gemeinderat sei anzuweisen, die nachträgliche Baueinsprache zu behandeln und ein nachträgliches Baubewilligungsverfahren durchzuführen. Eventualiter sei die Angelegenheit an das Verwaltungsgericht zurückzuweisen.
Das Verwaltungsgericht und die Beschwerdegegner beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Regierungsrat beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter, sie sei abzuweisen. Der Gemeinderat Feusisberg hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführer halten in ihrer Stellungnahme dazu im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. Während der Regierungsrat auf eine weitere Vernehmlassung verzichtete, nahmen das Verwaltungsgericht und der Gemeinderat Feusisberg zur Replik der Beschwerdeführer Stellung. Der Gemeinderat beantragte dabei die Abweisung der Beschwerde. Mit Schreiben vom 30. April 2012 informieren die Beschwerdeführer darüber, dass sie ihre Liegenschaft am 16. April 2012 verkauft haben. Die Beschwerdegegner äussern in einer weiteren Eingabe die Ansicht, dass aufgrund dieses Verkaufs die Legitimation der Beschwerdeführer wegfalle und deshalb auf die Beschwerde nicht einzutreten sei.

Erwägungen:
1. Dem angefochtenen Entscheid liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zugrunde. Nach Art. 34 Abs. 1 RPG (SR 700) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach Art. 82 lit. a BGG steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält keinen Ausschlussgrund (Art. 83 BGG). Angefochten ist ein Entscheid einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d BGG). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen, sind als Nachbarn durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (Art. 89 Abs. 1 BGG). Der Umstand, dass die Beschwerdeführer ihre Liegenschaft mittlerweile verkauft haben, ändert nichts an ihrer Beschwerdelegitimation (Art. 71 BGG i.V.m. Art. 21 Abs. 2 BZP; Urteil 1C_32/2007 vom 18. Oktober 2007 E. 1.1; <ref-ruling> E. 1b S. 223; je mit Hinweisen).
Die Beschwerdeführer bezeichnen ihre Eingabe als Verfassungsbeschwerde. Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten das zutreffende Rechtsmittel; die subsidiäre Verfassungsbeschwerde erweist sich deshalb als unzulässig (Art. 113 BGG). Die unrichtige Bezeichnung des Rechtsmittels schadet den Beschwerdeführern jedoch nicht. Die subsidiäre Verfassungsbeschwerde kann vorliegend in eine Beschwerde in öffentlich-rechtlichen Angelegenheiten konvertiert werden (<ref-ruling> E. 1.2 S. 382; 133 II 396 E. 3.1 S. 399; je mit Hinweisen). Auf die Beschwerde ist einzutreten.
2. 2.1 Die Beschwerdeführer machen geltend, sie hätten im vorinstanzlichen Verfahren einen Augenschein verlangt. Indem das Verwaltungsgericht davon abgesehen habe, habe es Art. 29 Abs. 2 BV und Art. 6 Ziff. 1 EMRK verletzt.
2.2 In seiner Vernehmlassung zuhanden des Bundesgerichts legt das Verwaltungsgericht dar, die Beschwerdeführer hätten nicht einen Augenschein, sondern eine mündliche Verhandlung beantragt. Mit Eingabe vom 27. Juli 2011 hätten sie auf die Durchführung einer mündlichen Verhandlung verzichtet, ohne dabei einen Augenschein auch nur zu erwähnen. Aus diesem Grund und zumal ohnehin keine zusätzlichen Erkenntnisse zu erwarten gewesen seien, sei auf die Durchführung eines Augenscheins verzichtet worden.
2.3 Die Verfahrensakten bestätigen die Argumentation des Verwaltungsgerichts. Zwar bringen die Beschwerdeführer in ihrer Eingabe vom 14. März 2012 an das Bundesgericht vor, sie hätten wohl auf die mündliche Verhandlung verzichtet, nicht aber auf den Augenschein. Dies ist jedoch aufgrund der Wortwahl in ihren Eingaben an die Vorinstanz nicht nachvollziehbar. In ihrer Beschwerde an das Verwaltungsgericht verlangten sie die Durchführung einer mündlichen Verhandlung und in ihrer Eingabe vom 27. Juli 2011 verzichteten sie wieder darauf. Unbesehen davon, ob der Antrag auf Durchführung einer mündlichen Verhandlung als einen Augenschein umfassend anzusehen ist, durfte das Verwaltungsgericht nach Treu und Glauben davon ausgehen, dass die Beschwerdeführer ihren Prozessantrag zurückgezogen hatten (Art. 5 Abs. 3 BV). Die Rüge der Verletzung von Art. 29 Abs. 2 BV und Art. 6 Ziff. 1 EMRK ist unbegründet.
3. 3.1 Das Verwaltungsgericht hielt im angefochtenen Entscheid fest, eine nachträgliche Baueinsprache sei aufgrund von § 80 Abs. 3 des Planungs- und Baugesetzes des Kantons Schwyz vom 14. Mai 1987 (SRSZ 400.100; im Folgenden: PBG) nicht zulässig gewesen. Vorausgesetzt sei nach dieser Bestimmung, dass die baulichen Vorkehren aus dem Baugespann und den aufgelegten Plänen nicht deutlich ersichtlich waren oder ihnen widersprechen. Die Beschwerdeführer hätten es selbst zu vertreten, dass sie die öffentlich aufliegenden Pläne nicht konsultiert haben. Im Übrigen führte das Verwaltungsgericht aus, dass nach § 78 Abs. 2 PBG Attikageschosse im Baugespann nicht sichtbar gemacht werden müssen. Das Baugespann müsse die geplante Baute nur in groben Zügen darstellen.
Im Sinne einer Alternativbegründung hielt das Verwaltungsgericht fest, es sei davon auszugehen, dass die Beschwerdegegner den Beschwerdeführern die Baupläne bereits vor Einreichung des Baugesuchs gezeigt haben. Unter diesen Voraussetzungen sei es rechtsmissbräuchlich, eine nachträgliche Baueinsprache zu erheben.
3.2 Die Beschwerdeführer rügen eine willkürliche Anwendung von § 78 Abs. 2 und § 80 Abs. 3 PBG. Auch wenn zutreffe, dass ein Baugespann nicht jede Einzelheit aufzeigen müsse, so sei doch vorliegend bei einem Attikageschoss von 12 m Länge, 11 m Breite und 3 m Höhe, das einen Drittel der Gesamthöhe der Baute ausmache, nicht von einem Detail auszugehen. § 80 Abs. 3 PBG müsse dahingehend interpretiert werden, dass sowohl die Pläne als auch das Baugespann ein korrektes Bild der künftigen Baute wiedergeben müssten. Ansonsten würde § 78 Abs. 2 entbehrlich, weil dem Baugespann dann keine Bedeutung mehr zukäme. Zu berücksichtigen sei auch, dass sie die Pläne bei einer Konsultation ohnehin falsch interpretiert hätten, da sie sich aufgrund der Aufschüttung die wahre Höhe der Baute im Terrain gar nicht hätten vorstellen können. Die Angabe der Höhenkoten in den Plänen sei diesbezüglich für Laien kaum hilfreich. Die Beschwerdeführer bringen weiter vor, es stelle eine willkürliche Tatsachenbehauptung dar zu sagen, dass eine nachträgliche Baueinsprache gestützt auf die fehlende Darstellung des Dachbereichs im Baugespann unzulässig sei. Ebenso sei das Argument willkürlich, sie hätten einfach bis zur Realisierung der bewilligten Baupläne zugewartet, statt die Auflagefrist zur Einsichtnahme zu nutzen.
Die Beschwerdeführer bestreiten auch, rechtsmissbräuchlich gehandelt zu haben. Es treffe zu, dass die Beschwerdegegner ihnen Pläne des Bauvorhabens gezeigt hätten. Diese seien damals jedoch noch in der Entstehungsphase gewesen und hätten keine Höhenkoten und Terrainangaben enthalten. Zudem sei es bei jenem Gespräch nicht um die Baute selbst, sondern um den Zugang zu einem Regenbecken gegangen.
3.3 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 S. 5 mit Hinweisen).
3.4 Gemäss § 78 Abs. 2 PBG hat das Baugespann die künftige Gestalt und räumliche Ausdehnung der Baute oder Anlage sowie die Terrainveränderungen aufzuzeigen. Es erscheint fraglich, ob ein Attikageschoss nach dieser Bestimmung nicht im Baugespann zu berücksichtigen ist. Die Ausmasse des Attikageschosses sind im Vergleich zu Dachaufbauten wie Kaminen, Giebelgauben, Dacherkern und dergleichen (vgl. dazu CHRISTOPH FRITZSCHE/PETER BÖSCH, Zürcher Planungs- und Baurecht, 4. Aufl., 2006, Titel 13.6) beträchtlich und zudem im Baugespann relativ leicht darzustellen (maximal sind vier zusätzliche Stangen notwendig). Im vorliegenden Fall ist diese Frage jedoch nicht entscheidend, da es ausschliesslich darum geht, ob eine nachträgliche Baueinsprache zulässig ist. Nach § 80 Abs. 3 PBG sind spätere Einsprachen zulässig, wenn die baulichen Vorkehren aus dem Baugespann und den aufgelegten Plänen nicht deutlich ersichtlich waren oder ihnen widersprechen. Eine grammatikalische Auslegung legt den Schluss nahe, dass der Mangel sowohl die Pläne als auch die Profilierung beschlagen muss. Das Interesse des Bauherrn an der Rechtssicherheit beziehungsweise am Vertrauensschutz bestätigt ein derartiges, für den Einsprecher restriktiv wirkendes Verständnis. Denn die nachträgliche Einsprache erfolgt in aller Regel während der Bauphase, in einem Zeitpunkt also, wo der Bauherr bereits erhebliche Investitionen getätigt hat, die er nicht ohne Nachteil wieder rückgängig machen kann. Wer nicht während der Auflagefrist Einsprache erhoben hat, soll dies deshalb nachträglich nur tun können, wenn er zuvor bei der Wahrnehmung seiner Interessen alle Sorgfalt hat walten lassen. Ein Blick auf das Baugespann ist insofern nicht ausreichend, sondern es ist eine Konsultation der Pläne erforderlich. Die Beschwerdeführer haben dies unterlassen. Sie deuten in dieser Hinsicht zwar an, dass sie die Pläne kaum richtig hätten interpretieren können, machen aber nicht geltend, dass die von ihnen angesprochene Terrainveränderung auf den Plänen nicht ersichtlich oder nicht ausgesteckt worden sei. Unter diesen Voraussetzungen ist dem Verwaltungsgericht keine Willkür vorzuwerfen, wenn es die nachträgliche Einsprache als unzulässig bezeichnete. Die betreffende Rüge der Beschwerdeführer ist unbegründet. Unbegründet ist damit auch die unter dem Titel "willkürliche Tatsachenbehauptung" vorgetragene Kritik der Beschwerdeführer, welche sich inhaltlich mit der Rüge der willkürlichen Anwendung von § 80 Abs. 3 PBG deckt.
Bei diesem Ergebnis kann offen bleiben, wie es sich mit der Alternativbegründung des Verwaltungsgerichts verhält, wonach den Beschwerdeführern auch wegen Rechtsmissbrauchs die Möglichkeit der nachträglichen Einsprache verwehrt sei.
4. Die Beschwerde ist abzuweisen. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 BGG). Die Beschwerdeführer haben den anwaltlich vertretenen Beschwerdegegnern eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Gemeinderat Feusisberg, dem Regierungsrat und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, schriftlich mitgeteilt.
Lausanne, 8. Juni 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold