I found a use of the phrase that predates the Maggie reference by a decade in an 1884 student publication of the University of Michigan called The Chronicle. It occurs at the end of a short story about a man courting a woman who says she cannot marry him but won't tell him why. Finally she tells him it is because she has cold feet. It is italicized in the original as if some sort of punch line to a joke:
"No, Ernest; I have already told you that I do not love another; but do not break my heart. Leave me forever. It can never be as you desire."
"Do not ruin me, Evelyn, but let me know why we must part."
"Alas! Ernest, I cannot, I must not tell you."
"But my dear Evelyn—"
"Oh, Ernest, forgive me, leave me. It can never be, I have cold feet."
I also found the story of the German card player, or at least a version of it. This is from An Old Story of My Farming Days: (Ut Mine Stromtid), by Fritz Reuter, (translation date 1878):
They played in the most friendly manner, till the rector who had arranged his money in a half circle, found out that he had won ten shillings, and then seeing that fortune was beginning to go against him, determined to stop playing; he therefore rose, and complaining of his feet having grown very cold, put his winnings in his pocket.—"If you suffer from cold feet," said Brasig, "I'll tell you an excellent cure; take a pinch of snuff every morning before you have eaten anything and that'll prevent your ever having cold feet." — "Nonsense!" cried Kurz, who had been winning, "what's to make his feet cold?" —"Why," said the rector, defending himself, "can't I have cold feet as well as you? Don't you always complain of having cold feet at the club when you've been winning?" And so Baldrian succeeded in keeping his right to cold feet and to what he had won.
Interestingly, there is another reference to cold feet in another book by Fritz Reuter called Seed-time and Harvest, also 1878, as some sort of joke involving a shoemaker:
"Children, my feet are getting cold," said Bank, the shoemaker, "I am going home."
"What? You may as well wait till the business comes to a head," said Thiel, the cabinet-maker.
"What do you know about it?" said Bank. "It seems to me as if there was'nt a word of truth in the whole story."
"What? You told me the story, yourself, this morning," said Thiel.
"Yes, that is so, but morning talk is not evening talk. I have considered the matter since then."
"That is to say, you have got cold feet over it," said the tailor. All laughed.
"That is a stupid joke," said the shoemaker, "and the whole story is a stupid joke; the old inspector has traded with me all these years, and has always paid his accounts honestly, and is he likely, in his old age, to take to cheating and stealing?"
Unfortunately, none of these references shed much light on why the phrase came to mean what it did. At least not for me. I thought the references were important enough to include here, though, and maybe someone else (a German speaker?) can take the pieces and complete the puzzle.
Edit, 6/28/11:
After doing a little more work on trying to figure out the intended humor of The Chronicle story quoted above, I came up with something that may shed more light on the phrase.
What I found was this reference in an issue of the Otago Daily Times from 1881:
After a little more sleuthing, I found that this maxim was quite common among Presbyterians, at least, in the 1880s. The idea being that missionary zeal needed to be paired with a concern for meeting the social needs of those to be converted. Apparently the original phrase went something along the lines of "Man cannot be converted while suffering from cold feet or an empty stomach." I've seen the phrase attributed to a half dozen different ministers in the early 1800s—it seems no one knew for sure who first said it. The important part is that the saying was commonly known in certain circles. Given that, and given that the University of Michigan was co-founded by a Presbyterian minister and probably still heavily populated by Presbyterians in 1884, I think the joke of the The Chronicle story may be a play on this religious maxim. In other words, since Evelyn has cold feet, she cannot be "converted" to the idea of marrying Ernest.
If this is the case (and I realize it could be a big "if") then I think there may also be the possibility that our modern idea of having cold feet could have been influenced by this same phrase. That is, as a corollary to not being interested in being "saved" when one's feet are cold, one's having "cold feet" may have come to mean one's reluctance to pursue a matter—perhaps popularized with jokes like the story above.