Sachverhalt: A. Am 9. November 2006 entdeckte der Vater von Y._ eine "Chatunterhaltung" auf ihrem Computer, die sie am Vortag mit einer unbekannten Person geführt hatte. Darin erzählte sie, sie sei im Sommer 2005 durch K.O.-Tropfen gefügig gemacht und von acht Männern vergewaltigt worden. Der Vater meldete in der Folge der Polizei, Y._ sei von X._ und dessen Freunden mehrmals zum Geschlechtsverkehr sowie oralem Sex gezwungen worden. Diese Handlungen seien mit Handys gefilmt worden. Die polizeiliche Untersuchung förderte noch weitere Delikte zu Tage, die im vorliegenden Verfahren nicht mehr angefochten sind. Das Beweisverfahren ergab gemäss Vorinstanz, dass X._ am 16. Juli 2005 im Rahmen einer Gruppenvergewaltigung ("Gang Bang") unter Anwesenheit mehrerer Kollegen Y._ vergewaltigt und zu weiteren sexuellen Handlungen wie Analverkehr genötigt hatte. B. Das Bezirksstrafgericht Sense verurteilte X._ am 18. März 2008 wegen Vergewaltigung, sexueller Nötigung und versuchter Vergewaltigung, begangen am 16. Juli 2005 zum Nachteil von Y._; mehrfachen sexuellen Handlungen mit zwei Kindern, begangen zwischen Dezember 2005 und November 2006; sexueller Nötigung, begangen im April/Mai 2006; Förderung der Prostitution, begangen im Herbst 2006 sowie mehrfachen Fahrens in fahrunfähigem Zustand, begangen am 9. März 2007 und 3. Juni 2007, zu einer Freiheitsstrafe von 3 1⁄2 Jahren, teilweise als Zusatzstrafe zum Urteil des Untersuchungsrichteramtes III Bern-Mittelland vom 20. Oktober 2005. Zudem verpflichtete es X._, verschiedene Genugtuungszahlungen zu leisten. Das Verfahren wegen einfacher Körperverletzung stellte es ein. C. Der Strafappellationshof des Kantons Freiburg wies am 17. September 2009 die Berufung von X._ ab und bestätigte das angefochtene Urteil. X._ führte gegen das Urteil des Strafappellationshofs Beschwerde in Strafsachen. Das Bundesgericht hiess die Beschwerde am 13. Dezember 2010 gut und wies die Sache zur neuen Entscheidung an die Vorinstanz zurück. D. Der Strafappellationshof des Kantons Freiburg wirft X._ in seinem Entscheid vom 5. März 2012 vor, Y._ am 16. Juli 2005 nach einvernehmlichem Geschlechtsverkehr mit zwei weiteren Personen festgehalten und im Rahmen einer Gruppenvergewaltigung ("Gang Bang") unter Anwesenheit mehrerer Kollegen zu vergewaltigen versucht sowie zu weiteren sexuellen Handlungen genötigt zu haben. Der Strafappellationshof bestätigte die Schuldsprüche sowie die Genugtuungs- und Entschädigungszahlungen, sprach X._ aber vom Vorwurf der vollendeten Vergewaltigung frei. Er verurteilte ihn zu einer Freiheitsstrafe von 40 Monaten, teilweise als Zusatzstrafe zum Urteil des Untersuchungsrichteramtes III Bern-Mittelland vom 20. Oktober 2005. E. X._ führt Beschwerde in Strafsachen. Er beantragt, das angefochtene Urteil sei aufzuheben, und er sei vom Vorwurf der versuchten Vergewaltigung sowie sexueller Nötigung, begangen am 16. Juli 2005 zum Nachteil von Y._, freizusprechen. Für die übrigen Anklagepunkte sei er zu einer bedingten Freiheitsstrafe von 18 Monaten, bei einer Probezeit von zwei Jahren, zu verurteilen. X._ verlangt die unentgeltliche Rechtspflege und Verbeiständung. F. Das Kantonsgericht Freiburg beantragt sinngemäss, die Beschwerde sei abzuweisen. Die Staatsanwaltschaft des Kantons Freiburg und Y._ beantragen die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. 