Faits: A. X._, ressortissant Turc, né en 1963, est venu une première fois en Suisse comme requérant d'asile en 1986. Sa demande ayant été rejetée, une interdiction d'entrée lui a été signifiée jusqu'en 1990. Revenu illégalement en Suisse en 1996, il a épousé, le 2 avril 2001, à Neuchâtel, Y._, ressortissante suisse, née en 1945 en Tunisie, et a obtenu une autorisation annuelle de séjour, renouvelée jusqu'au 2 avril 2006. Le 28 janvier 2004, le Service des migrations du canton de Neuchâtel a rejeté la demande de regroupement familial présentée par X._ en faveur de ses deux filles restées en Turquie. Il a ensuite procédé à des investigations pour savoir si l'intéressé vivait régulièrement au domicile conjugal. Lors de son audition du 6 juillet 2006, X._ a déclaré être définitivement séparé de son épouse, suite à des problèmes conjugaux. Par décision du 6 juillet 2007, le Service des migrations a refusé à X._ l'octroi d'une autorisation d'établissement, ainsi que la prolongation de son autorisation annuelle de séjour. Il a retenu en bref que les époux s'étaient séparés à plusieurs reprises depuis 2001, et définitivement depuis le 15 octobre 2005, soit avant l'échéance du délai de cinq ans permettant l'octroi d'une autorisation d'établissement. Ce prononcé a été confirmé, sur recours, par décision du Département de l'économie publique du 7 août 2008. B. X._ a recouru contre la décision du Département de l'économie auprès du Tribunal administratif du canton de Neuchâtel, en alléguant qu'au mois de mai 2008, les époux avaient renoncé à divorcer et avaient envisagé de reprendre la vie commune. Par arrêt du 19 janvier 2008, le Tribunal administratif a rejeté le recours. Il a jugé que le recourant commettait un abus de droit en invoquant un mariage qui n'existait plus que formellement déjà avant le délai de cinq ans et que la renonciation de l'épouse à la procédure de divorce ne suffisait pas pour admettre un espoir de réconciliation. C. X._ forme un recours en matière de droit public auprès du Tribunal fédéral et conclut, avec suite de frais, à l'annulation de l'arrêt du Tribunal administratif du 19 janvier 2009. Il demande, principalement, l'octroi d'une autorisation d'établissement ou le renouvellement de son autorisation de séjour et, subsidiairement, le renvoi de l'affaire à l'autorité cantonale compétente pour qu'elle accorde les autorisations requises. Le Tribunal administratif se réfère à son arrêt et conclut au rejet du recours. Le Département de l'économie conclut au rejet du recours, dans la mesure où il est recevable, avec suite de frais. L'Office fédéral des migrations propose de rejeter le recours. D. Par ordonnance du Tribunal fédéral du 3 mars 2009, la demande d'effet suspensif présentée par le recourant a été admise. 