If there was a good reason to make the change, it must mean the available data is now different, which means the programs using it need to change.

No, that's the point. Likely some programs will change (or new programs written) that triggered the change. But may programs won't. Let's make an example. A bit contrieved perhaps, but it's just an example. Suppose you have a table of addresses, with the usual columns: an id, a key to another table telling you whose address it is, a street address, a city, a state (let's assume US addresses), a zip code, etc. It's an important table because many applications use it. There will be several stored procedures accessing this table, one of them being "get_address":

-- Sybase syntax
create proc   get_address @addressee int
as     select street_address, city, state, zip
       from   addresses
       where  @addressee = addressee_id  -- addressee_id is the foreig
+n key
[download]

Now a desire arises to separate the street address into two columns: the name of the street, and the house number. Maybe some application wants to do selects on a street - it doesn't really matter why. The schema can easily be changed, and a conversion program (that reads the table, and splits the street address into a street name and house number) isn't to hard either. Now, if all other programs used the stored procedure to get data out of the table, they don't need to be modified - we just change the stored procedure:

-- Sybase syntax
create proc   get_address @addressee int
as     select house_number + " " + street_name, city, state, zip
       from   addresses
       where  @addressee = addressee_id  -- addressee_id is the foreig
+n key
[download]

Note that the signature (the input and output formats) of the stored procedure didn't change. Obviously, applications that want to get the street name separately use different stored procedures.

Trying to hide changes like that behind stored procs and let programs continue as if nothing happened will surely result in slow and complicated joins and the like.

That all depends on how often queries are run, and when. A bank really doesn't care if its end of the week report that's run on the night from Saturday to Sunday now takes 7 hours and 10 minutes instead of the original 7 hours and 3 minutes. But they'll get mighty upset if one batch job every techy forgot about because it was written long before any of them started working there suddenly fails to work. Don't forget that changing the stored procedures doesn't prevent you from writing new (and faster) stored procedures and calling them from your programs. Stored procedures give you the option to leave programs as is if you modify the schemes.