It's complicated.
Both are correct (for certain definitions of "correct" and depending on the context). The first is more natural to me in normal speech. I would use the second in formal writing (because it has been drilled into me, not because it is natural). So it depends on the register you wish to communicate in.
The rules for pronoun case in coordinated structures like this are governed by many things. For example, whether they are both pronouns and, if not, whether the pronoun comes first or second.
There is a fairly detailed investigation in this thesis: “Me and her” meets “he and I”: Case, person, and linear ordering in English coordinated pronouns by Thomas Grano
Edit: Having finally had some time to look into this a bit more, I have found some interesting discussion on the Language Log blog:
The entry for me in Merriam-Webster's Dictionary of English Usage notes that:
...
While traditional opinion prescribes someone and I for subject use — I and someone seems a bit impolite — in actual practice we also find me and someone and someone and me […]
They then provide some data on the relative frequency of the various forms in some corpora and go on the speculate on the mechanisms ("rules") behind it. For example:
One theory would be that in some varieties of English me is an emphatic form rather than (or in addition to) an accusative form. Thus in the same way that French has "Jean et moi" rather than "*Jean et je", this kind of English has "John and me" rather than "*John and I".
(It is interesting to note that in French, moi is standard rather than je. I'm not sure what that says about the "logical" arguments presented in the other answers.)
One direction towards a solution might be to adopt the theory put forward in Joseph Emonds, "Grammatically deviant prestige constructions", 1986, and adopted e.g. by Nicholas Sobin, "Agreement, Default Rules, and Grammatical Viruses", Linguistic Inquiry 29(2) 1997. This theory says that "nominative" pronouns in coordinate subjects are actually ungrammatical in English ("grammatically deviant") and must be introduced by extra-grammatical editing rules ("grammatical viruses", in Sobin's terminology).
1) The natural state of all pronouns in coordinate subjects is accusative.
2) There is a rule (of prestigious deviance) turning "and me" into "and I".
There are many other references to information on the subject, and an interesting discussion in the comments section.