Sachverhalt: A. Das Bezirksgericht Zürich verurteilte am 28. April 2009 X._ wegen Schändung zum Nachteil von A._ mit einer unbedingten Freiheitsstrafe von 18 Monaten, unter Anrechnung von 164 Tagen Haft. Das Gericht stellte ausserdem die dem Grundsatz nach bestehende Schadenersatzpflicht von X._ fest. Zur genauen Feststellung des Umfangs des Schadenersatzanspruchs verwies es A._ auf den Zivilweg. Weiter verpflichtete es X._ zu einer Genugtuungszahlung von Fr. 8'000.-- zuzüglich Zinsen an A._. B. X._ erhob Berufung an das Obergericht des Kantons Zürich. Dieses bestätigte mit Urteil vom 12. Januar 2010 das erstinstanzliche Urteil. C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er verlangt, das vorinstanzliche Urteil sei aufzuheben, und er sei vollumfänglich freizusprechen. Ferner sei auf die adhäsionsweise geltend gemachte Zivilforderung nicht einzutreten. Ausserdem sei ihm die unentgeltliche Rechtspflege zu bewilligen und ihm Matthias Brunner als unentgeltlicher Rechtsbeistand zu bestellen. D. Die Vorinstanz sowie die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung. A._ beantragt, die Beschwerde sei abzuweisen und das vorinstanzliche Urteil unter Kosten- und Entschädigungsfolgen zulasten des Beschwerdeführers zu bestätigen. 