It's originally a surname from a place name in Cheshire, England, and according to Hanks & Hodges' A Dictionary of Surnames, the place name meant "Ceolmund's clearing". Ceolmund was an Old English given name formed from words meaning "ship" and "protection".
Though like most British surnames Cholmondeley may have been really used as a given name on rare occasions, I think that this one, like Murgatroyd, probably turns up more often for comic and cartoon characters than it does for real people. :)