There's a really interesting lecture by Michael Drout on the 4/16/10 iTunes feed for The Tolkien Professor podcast. Here's a sample:
Strider, who became Aragorn, was originally a hobbit named “Trotter,” who wore wooden shoes or had wooden feet even. (He’d been tortured by the Dark Lord and so had to wear shoes, or maybe even have prosthetic wooden feet.) And “Trotter” persisted forever. Meriadoc’s name was “Marmaduke.” And my favorite one is that Frodo was “Bingo” -- for a long time, I mean, like, multiple drafts. So what I tell my students is: revise, revise, revise ... Or actually, the other one is that in The Hobbit, Gandalf’s original name was “Bladderthin.” And again that persisted through whole drafts.