Sachverhalt: A. Die X._ SA, Y._, Z._ und die W._ AG sind bzw. waren auf dem Gebiet des Weinhandels tätig. Im August und im November 2011 führte die Eidgenössische Steuerverwaltung (ESTV) bei ihnen Kontrollen hinsichtlich der geschuldeten Mehrwertsteuer durch. Am 15. Dezember 2011 erliess die ESTV die "Einschätzungsmitteilung Nr. 311'955 / Verfügung" betreffend die Steuerperioden 1. Quartal 2005 bis 4. Quartal 2009. Darin hielt sie fest, dass die Einzelfirma Y._ rückwirkend per 1. Januar 2005, die Einzelfirma Z._ rückwirkend auf den 1. Juni 2006 und die W._ AG rückwirkend auf den 1. Juni 2007 aus dem Register der Mehrwertsteuerpflichtigen gelöscht würden, zumal sie zusammen mit der X._ SA als wirtschaftliche Einheit gelten und in ihrer Gesamtheit die steuerpflichtige Person X._ SA bilden würden. Diese schulde aufgrund der dadurch notwendigen Steuerkorrektur Mehrwertsteuern in Höhe von Fr. 1'434'477.-- zuzüglich Verzugszins. Ebenfalls am 15. Dezember 2011 erliess die ESTV eine zweite "Einschätzungsmitteilung Nr. 311'956 / Verfügung" betreffend die Steuerperiode 1. Quartal 2010 bis 4. Quartal 2010 und forderte von der X._ SA Mehrwertsteuern in Höhe von Fr. 234'018.-- zuzüglich Verzugszins. Im Übrigen entsprach diese Entscheidung inhaltlich der Einschätzungsmitteilung Nr. 311'955 betreffend die früheren Steuerperioden. Beide Einschätzungsmitteilungen machten in der Rechtsmittelbelehrung auf die Möglichkeit einer Einsprache aufmerksam. Auf entsprechendes Gesuch hin liess die ESTV der X._ SA, Y._, Z._ und der W._ AG am 25. Januar 2012 je eine Erläuterung der beiden Ergänzungsmitteilungen zukommen, worin sie erneut auf das Rechtsmittel der Einsprache hinwies und darauf aufmerksam machte, dass die Einsprachefrist mit der Erläuterung neu zu laufen beginne. B. Statt eine Einsprache zu erheben, wandten sich die X._ SA, Y._, Z._ und die W._ AG am 31. Januar 2012 mit einer als "Sprungbeschwerde" bezeichneten Eingabe ans Bundesverwaltungsgericht. Dieses erachtete die Voraussetzungen einer Sprungbeschwerde indes als nicht gegeben: Mit Urteil vom 31. Mai 2012 trat es auf die Beschwerde mangels funktioneller Zuständigkeit nicht ein und überwies die Angelegenheit an die ESTV. C. Mit Eingabe vom 4. Juli 2012 führen die X._ SA, Y._, Z._ und die W._ AG Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie stellen den Antrag, es sei das Bundesverwaltungsgericht anzuweisen, auf die Sprungbeschwerde einzutreten. Während das Bundesverwaltungsgericht auf eine Vernehmlassung verzichtet, schliesst die ESTV auf Abweisung der Beschwerde. Mit Eingabe vom 15. Oktober 2012 nehmen die Beschwerdeführer zum Vernehmlassungsergebnis Stellung.