Sachverhalt: A. A.A._ kaufte sich im Laufe des Jahres 2006 als unselbständig Erwerbender mit einem Betrag von Fr. 250'000.-- zur Finanzierung der vorzeitigen Pensionierung in die Vorsorgestiftung zugunsten des Personals der X._ AG ein. Nachdem er von Januar bis März 2009 Taggelder der Arbeitslosenversicherung bezogen hatte und sein Vorsorgekapital auf ein Konto der Freizügigkeitsstiftung Y._ hatte überweisen lassen, liess er sich am 7. April 2009 sein angespartes Kapital in der Höhe von Fr. yyy auszahlen. Als Grund für die Barauszahlung gab er die Aufnahme einer selbständigen Erwerbstätigkeit an. Dazu hatte er am 5. Januar 2009 das Einzelunternehmen Z._ mit Sitz in U._ (AG) in das Handelsregister eintragen lassen. Vor der Auszahlung hatte er sich am 1. April 2009 zusammen mit seiner Ehefrau und den beiden Kindern bei der Einwohnerkontrolle U._ ab- und in V._ (GR) angemeldet. Am 1. Oktober 2009 meldete sich die Familie erneut in U._ an. B. Mit Verfügungen vom 7. September 2010 besteuerten das Gemeindesteueramt V._ und die Steuerverwaltung des Kantons Graubünden die Kapitalzahlung für die Gemeinde, den Kanton und den Bund. Diese Verfügungen sind unangefochten in Rechtskraft erwachsen. C. C.a. Am 22. und 28. Februar 2013 besteuerte auch die Steuerkommission U._ die erfolgte Kapitalzahlung (Jahressteuer der Kantons- und Gemeindesteuern 2009 resp. der direkten Bundessteuer 2009 von je Fr. yyy). Die dagegen erhobenen Einsprachen sind noch pendent. C.b. Am 22. August 2013 veranlagte die Steuerkommission U._ die Ehegatten betreffend die Kantons- und Gemeindesteuern 2009 zu einem steuerbaren Einkommen von Fr. yyy und zu einem steuerbaren Vermögen von Fr. yyy (satzbestimmend Fr. yyy). Die Kapitalauszahlung vom 7. April 2009 erfasste sie dabei abweichend von den im Februar 2013 erlassenen Verfügungen als übriges Einkommen, da sie die Aufnahme einer selbständigen Erwerbstätigkeit nicht als gegeben und damit die Voraussetzungen für eine Barauszahlung nicht als erfüllt erachtete. Die dagegen erhobenen Rechtsmittel blieben erfolglos (Einspracheentscheid der Steuerkommission vom 30. Oktober 2013; Entscheid des Spezialverwaltungsgerichts des Kantons Aargau, Abteilung Steuern, vom 25. Juni 2015; Urteil des Verwaltungsgerichts des Kantons Aargau vom 27. Januar 2016). D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 2. März 2016 beantragen A.A._ und B.A._ die Aufhebung der interkantonalen Doppelbesteuerung für die Kapitalzahlung aus Vorsorge, indem das Urteil des Verwaltungsgerichts aufgehoben und der Kanton Aargau angewiesen werde, die Kapitalzahlung bei der Bestimmung des steuerbaren Einkommens der Steuerperiode 2009 von der Besteuerung auszunehmen. Eventualiter sei die Veranlagungsverfügung des Kantons Graubünden vom 7. September 2009 (recte: 2010) bezüglich der Sondersteuer auf Kapitalabfindung des Kantons Graubünden und der Gemeinde V._ aufzuheben und der Kanton Graubünden und die Gemeinde V._ anzuweisen, ihnen die bezahlten Steuern samt Vergütungszins zurückzuerstatten. Das Verwaltungsgericht und das Kantonale Steueramt des Kantons Aargau beantragen die Abweisung der Beschwerde. Die ESTV hat sich - ohne einen Antrag zu stellen - vernehmen lassen. Die ebenfalls zur Vernehmlassung eingeladene Steuerverwaltung des Kantons Graubünden beantragt die Gutheissung der Beschwerde, eventualiter die Gutheissung des Eventualantrags der Beschwerdeführer.