Faits: A. A._ est née à Genève, le 6 mars 2004, de la relation hors mariage entre dame X._, née le 13 décembre 1971, et Y._, né le 7 juillet 1969, qui a reconnu sa paternité par acte d'état civil du 1er décembre 2003. Sur requête des parents qui ont décidé de ne plus poursuivre la vie commune, le Tribunal tutélaire du canton de Genève a notamment, par ordonnance du 6 octobre 2006, attribué à ceux-ci l'autorité parentale conjointe sur leur fille, dit que la garde de l'enfant était confiée à la mère en cas de dissolution du ménage et fixé les modalités du droit de visite du père ainsi que la contribution d'entretien mise à sa charge. Le père s'est constitué un nouveau domicile à B._ (GE) à la fin du mois de novembre 2006. Les parents travaillent tous deux dans cette commune, où ils résidaient lorsqu'ils vivaient ensemble et où l'enfant a fréquenté une crèche jusqu'en septembre 2007. Depuis cette date, la fillette a été scolarisée en France voisine par sa mère, dans une école privée située à proximité de B._. Par ordonnance du 5 octobre 2007, le Tribunal tutélaire a fait droit à une nouvelle demande des parents tendant au prononcé d'une garde alternée, à raison d'une semaine sur deux chez l'un et chez l'autre, et de la moitié des vacances scolaires. Cette autorité s'est en particulier fondée sur un rapport du Service de protection des mineurs (ci-après: SPMi) du 27 septembre 2007, préconisant la ratification de la convention déposée par les parents qui avaient, d'ores et déjà, instauré une garde alternée de fait. En mars 2008, la mère s'est établie avec l'enfant chez son compagnon en France voisine. A teneur d'une attestation de l'Office cantonal de la population, elle est toutefois officiellement domiciliée avec sa fille chez ses parents, à Z._ (GE). B. Par requête du 8 février 2008 adressée à l'Autorité de surveillance des tutelles du canton de Genève, la mère a demandé le retrait, à son seul profit, de l'autorité parentale sur l'enfant détenue par le père, ainsi que l'attribution de la garde, un droit de visite usuel étant réservé au père. Celui-ci s'est opposé à ces conclusions et a sollicité, reconventionnellement, l'attribution des droits parentaux en sa faveur, un droit de visite usuel étant réservé à la mère. Aux dires des parties devant cette autorité ainsi qu'à teneur d'un nouveau rapport du SPMi du 5 mai 2008, le système de garde alternée a cependant continué de bien fonctionner. Par arrêt du 19 août 2008, l'Autorité de surveillance des tutelles a déclaré irrecevables les conclusions des parties tendant à l'attribution en leur faveur respective de la garde de l'enfant et à la réglementation du droit de visite, a retiré à la mère l'autorité parentale sur la fillette et a transmis le dossier au Tribunal tutélaire pour qu'il statue sur le droit de garde et sur les relations personnelles. C. La mère interjette un recours en matière civile au Tribunal fédéral contre l'arrêt du 19 août 2008, dont elle demande l'annulation. Elle conclut principalement à l'attribution à son seul profit de l'autorité parentale, celle octroyée au père lui étant retirée, et au maintien de la garde alternée. Subsidiairement, elle demande la transmission de la cause au Tribunal tutélaire pour qu'il statue sur les modalités de la garde de l'enfant ainsi que sur le droit de visite du père. L'intimé propose le rejet du recours. Il sollicite en outre le bénéfice de l'assistance judiciaire. D. Par ordonnance du 16 octobre 2008, la présidente de la cour de céans a déclaré la requête d'effet suspensif sans objet, en application de l'art. 103 al. 2 let. a LTF. E. La présente cause a fait l'objet d'une délibération publique le 27 août 2009. 