When I was studying Spanish in Cuba last summer (July 2003), my professor told us that in the early 1500s, the native (Ciboney?) chief of the region around the current city of La Habana was named Habanaguex. From what I've found online, apparently Habanaguex was friendly to the Spaniards, who identified him with the region, and so when the Spanish Catholics founded city on Saint Christopher's day somewhere around 1514, they named it San Cristóbal de La Habana, which is still its official name.
In Spanish, the "v" and "b" are pronounced almost identically, so the Anglicized version of La Habana became Havana.
(Sorry, I also posted most of this elsewhere before realizing where the thread started.)