Paste Formula Problem

I've got a problem that is driving me crazy. I'm about to give up and do it the hard way. But I'll ask for your help first. Here it is:

I've got a range of cells in a worksheet - some with values, some with formulas. There is 20 other sheets in the book - all identical, except for the values.

Anyhow, I've re-done a number of the formulas in one sheet (very time consuming) and I want to paste the new formulas over the old ones in all the other sheets - but I do not want to change any of the cells with existing data. I only want to change the cells that have formulas.

Problem is, in order to do only one single copy/paste per sheet, I have to select a continuous range of cells. However, this continuous range has also cells with only values in them. Therefore when I paste the range, not only do I get my new formulas pasted (good), I also get the values pasted (bad).

The strange thing is that even if I choose paste/special/formulas, I also wind up pasting over any values! Thereby ruining the data.

In my opinion, paste formulas should read "paste formulas AND values, but not formatting."

What can be done about this?

Thanks a lot