Faits:
A. Par jugement du 11 décembre 2008, le Juge I du district de Conthey a condamné X._, pour acte d'ordre sexuel avec des enfants et conduite sans permis de conduire, à une peine privative de liberté de 12 mois, avec sursis pendant 2 ans, peine partiellement complémentaire à une peine de 30 jours d'emprisonnement avec sursis pendant 3 ans et à une amende de 700 fr. prononcée le 11 mars 2005 et à une peine de 2 mois d'emprisonnement avec sursis pendant 4 ans et une amende de 1'000 fr. prononcée le 24 novembre 2006.
Ce jugement a été confirmé sur appel par le Juge de la Cour pénale II du Tribunal cantonal valaisan, qui a cependant réduit la peine privative de liberté de 12 à 8 mois.
B. Cette condamnation repose, en bref, sur les éléments suivants.
B.a A la fin du mois de septembre 2004, Y._, née en 1989, a passé quelques jours de vacances dans la famille d'une amie de son âge. Les deux jeunes filles se sont intéressées à un jeune homme blond travaillant sur un chantier non loin de leur lieu de vacances. Par jeu, elles ont discrètement posé un billet dans le véhicule de l'entreprise de construction en demandant à l'inconnu de prendre contact par SMS avec Y._. Lors des échanges SMS, celle-ci a indiqué qu'elle avait 16 ans et son interlocuteur a répondu qu'il en avait 24.
Le jour des faits, cachée derrière un arbre sur le chantier, Y._ a envoyé un SMS et s'est aperçue que son interlocuteur n'était pas le jeune homme blond, mais X._. Alors que son amie voulait interrompre le jeu, Y._ s'est dirigée vers l'intéressé, qui l'a invitée à le suivre dans les sous-sols de la construction. Après avoir discuté de tout et de rien, X._ l'a embrassée et s'est rendu compte qu'elle était inexpérimentée. Il n'a pas questionné l'adolescente sur son âge. Il l'a déshabillée et caressée sur tout le corps. Il s'est dévêtu et a exhibé son pénis, s'est masturbé et s'est fait faire une fellation. Il lui a indiqué comment procéder. Il a eu envie de la pénétrer, lui a demandé si elle était vierge, lui a caressé les seins, lui a touché le clitoris avec le pénis et lui a demandé de se détendre, car il avait constaté que la jeune fille était crispée. Il s'est rendu compte que c'était la première relation sexuelle complète qu'entretenait l'adolescente, l'a pénétrée sans protection, après avoir constaté qu'elle avait ses règles, et a éjaculé en elle et sur son sexe. X._ s'est ensuite excusé auprès de Y._ et l'a embrassée.
B.b X._ a toujours prétendu que la jeune fille était consentante, ce que cette dernière a nié de façon constante. Elle a expliqué avoir été saisie d'effroi, ne sachant ce qui allait arriver si elle résistait et avoir protesté verbalement au fur et à mesure que son partenaire devenait plus pressant, ne voyant pas la possibilité d'y échapper physiquement. Lors de l'acte sexuel, la jeune fille a affirmé avoir dit « non » et manifesté sa douleur. Elle a subi un examen gynécologique le soir même.
C. X._ forme un recours en matière pénale concluant à son acquittement du chef d'accusation d'acte d'ordre sexuel avec des enfants et au renvoi du dossier pour nouvelle décision. Il invoque une violation du principe "in dubio pro reo" et de l'<ref-law>.

Considérant en droit:
1. Le recourant invoque l'interdiction de l'arbitraire dans l'établissement des faits et la violation du principe "in dubio pro reo" découlant de la présomption d'innocence. Il ne soutient pas qu'un doute subsisterait après l'examen des preuves. Il tente de démontrer que les autorités cantonales auraient dû en éprouver un en les appréciant sans arbitraire (sur cette notion: cf. <ref-ruling> consid. 1.3 p. 4 s.). Ces griefs se confondent sous cet angle (<ref-ruling> consid. 2a p. 88). Cependant, l'argumentation du recourant revient à opposer son opinion à celle de la Cour cantonale et ne répond pas aux exigences accrues de motivation découlant de l'<ref-law>. Elle est appellatoire, partant déjà irrecevable pour cette raison (<ref-ruling> consid. 6 p. 397). De plus, elle porte sur l'éventuel consentement de la victime aux actes d'ordre sexuel, fait qui n'est pas pertinent en l'espèce et qui échappe, par conséquent, à l'examen du TF (<ref-law>).
2. Le recourant invoque une violation de l'<ref-law>.
2.1 L'<ref-law> punit celui qui aura commis un acte d'ordre sexuel avec un enfant de moins de 16 ans. Le chiffre 4 de cette disposition précise que la peine sera une peine privative de liberté de trois ans au plus ou une peine pécuniaire si l'auteur a agi en admettant par erreur que sa victime était âgée de 16 ans au moins, alors qu'en usant des précautions voulues, il aurait pu éviter l'erreur.
Les éléments objectifs de l'<ref-law> étant réunis et non contestés par le recourant, la seule question qui se pose est de savoir si le recourant a usé des précautions voulues (<ref-law>), c'est-à-dire s'il a fait preuve ou non preuve de négligence au sens de l'<ref-law>. Dans un tel cas, cette disposition, lorsqu'on est proche des limites légales, doit être interprétée généreusement (<ref-ruling> consid. 3). Savoir si l'auteur était dans l'erreur est une question de fait, mais savoir si l'erreur était évitable est une question de droit (<ref-ruling> consid. 2a; <ref-ruling> consid. 1 p. 232). Pour savoir si l'erreur était évitable, l'aspect de la personne, sa taille, les traits de son visage et son développement corporel sont déterminants (cf. arrêt 6B_214/2007 du 13 novembre 2007 consid. 3.3).
2.2 En l'espèce, tel que cela ressort de l'arrêt attaqué, auquel la cour de céans est liée et dont le recourant n'est pas admis à s'écarter, la jeune fille était âgée de 15 ans et 5 mois et demi au moment des faits et le recourant s'est fié au SMS de celle-ci, lui indiquant qu'elle avait 16 ans. La victime avait une apparence extrêmement juvénile et portait encore les traces de l'enfance. Aussi bien son physique, que l'âge limite dont elle avait parlé par SMS, devaient inciter le recourant à la circonspection, ce d'autant plus que les faits se sont déroulés lors de la première rencontre des protagonistes. A cela s'ajoute que la jeune fille avait dit au recourant qu'elle était étudiante et qu'elle allait à l'école et que celui-ci a immédiatement remarqué son inexpérience manifeste lorsqu'il l'a embrassée, ce qui l'a amené à lui demander si elle était vierge. Le recourant étant âgé de 25 ans au moment des faits, on ne peut plus parler d'une manifestation d'« amour juvénile ». Au contraire, l'intéressé était déjà marié et père de famille et ne connaissait pas sa jeune victime, avec laquelle il avait uniquement échangé quelques SMS et propos juste avant les faits. Au regard de l'ensemble de ces éléments, on peut reprocher au recourant d'avoir fait preuve de légèreté, en ne s'enquérant même pas de l'âge de la jeune fille ou en ne se renseignant pas davantage et en se fiant, sans autre investigation, au SMS de cette dernière ou au fait qu'elle lui ait dit qu'elle était étudiante et qu'elle allait à l'école, ce qui n'excluait aucunement qu'elle n'ait pas encore 16 ans, avant de céder à son excitation et de commettre des actes d'ordre sexuel avec elle.
Pour le reste, un éventuel consentement de la victime aux actes d'ordre sexuel commis n'a aucune incidence sur l'appréciation de la légèreté de l'auteur. Sanctionner le comportement du recourant, qui n'entre pas dans la catégorie des amours dits juvéniles visés par le législateur, non seulement ne contrecarre pas la volonté de ce dernier, qui voulait se montrer moins rigoureux à l'égard de jeunes auteurs qui étaient des camarades proches (FF 1985 II 1083ss), ce qui n'est pas le cas du recourant et de sa victime, mais encore ne procède pas d'une interprétation trop rigoureuse de la notion de négligence. La solution contraire conduirait à admettre l'absence de négligence, dès que la jeune victime aurait écrit une fois, lors d'un échange de SMS, avoir 16 ans, alors que d'autres indices évidents mettaient en doute sa déclaration, ce qui serait alors contraire au but du législateur de protéger le développement des adolescents, même contre leur volonté. Dans ces conditions, les autorités valaisannes n'ont pas violé le droit fédéral en appliquant l'<ref-law>.
3. Le recours doit ainsi être rejeté dans la mesure où il est recevable. Le recourant, qui succombe, supportera les frais judiciaires (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, fixés à 4'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Le Juge de la Cour pénale II.
Lausanne, le 3 juin 2010
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Bendani