Answer: It's a great story, but it's just that: a story. More precisely it's an urban legend, one of those stories that is repeated so often that people come to believe it. Like many other legends, it has enough truth (some Spaniards indeed do speak with something resembling a lisp, at least to those accustomed to the pronunciation of Latin American Spanish) to be believed, provided one doesn't examine the story too closely. (In this case, looking at the story more closely would make one wonder why Spaniards don't also pronounce the letter s with a so-called lisp.)
The fact is that all living languages evolve. And when one group of speakers is separated from another group, over time the two groups will part ways and develop their own peculiarities in pronunciation, grammar and vocabulary. Just as U.S. English differs from British English (both of which differ from Canadian and South African English, among others), so does the Spanish of Spain and various Latin American countries. Even within one country, including Spain, you'll hear regional variations in pronunciation. And that's all we're talking about with the "lisp." Some people in Spain (and even in a few parts of South America) pronounce the letter z roughly the same as the English "th" of "tooth," while others pronounce it like an "s." It's not a lisp; it's just a difference in pronunciation.
Addendum: There isn't always a specific explanation of why language changes in the way it does. But there is a plausible explanation given for this change, according to a graduate student who wrote to this site after this question and answer were first published. Here's what he said:
"As a graduate student of the Spanish language and a Spaniard, being confronted with people who 'know' the origin of the 'lisp' found in most of Spain is one of my pet peeves. I have heard the 'lisping king' story many times, even from cultured people who are native Spanish speakers, though you will not hear it come from a Spaniard.
"Firstly, the ceceo is not a lisp. A lisp is the mispronunciation of the sibilant s sound. In Castilian Spanish, the sibilant s sound exists and is represented by the letter s. The ceceo comes in to represent the sounds made by the letters z and c followed by i or e.
"In medieval Castilian there were two sounds that eventually evolved into the ceceo, the ç (the cedilla) as in plaça and the z as in dezir. The cedilla made a /ts/ sound and the z a /dz/ sound. This gives more insight into why those similar sounds may have evolved into the ceceo."
Note on terminology: In the above student comment, the term ceceo is used to refer to the pronunciation of the z (and of c after e or i). To be precise, however, the term ceceo refers to how the s is pronounced, namely the same as the z of most of Spain — so that, for example, sinc would be pronounced like roughly "think" instead of like "sink." In most regions, this pronunciation of the s is considered substandard. When used precisely, ceceo doesn't refer to the pronunciation of the z, ci or ce, although that error is often made.