I have an excel sheet with about 10,000 text cells. 

Many of them contain errors which I normally "Find and Replace."
However, these entries are about twenty lines long, and though I can
find them, I can not replace them in bulk. It tells me that the
"Formula is too long"

I need precise directions as to how to solve this problem.  If I need
to buy an add-on, please let me know what to buy.

Please do not answer if you tell me it "can't be done".  If no one
responds, I'll presume it can't be done.  Thanks.

I understand that Excel formulas used to be limited to about 128 or
255 characters or so. They may now be limited to about 1023 or some
such figure.

The find and replace function may be encountering problems because one
of these limits is exceeded. Your solutions could be:
(a) Write a Visual Basic Macro that runs through each cell and does a
visual basic equivalent of find and replace using visual basic string
commands. You may need to read the visual basic for Excel help files
to work out how to do this. The Macro Recorder can be used to produce
some starter code for a macro that you can then edit.
(b) Export all the data to WORD as a TAB delimited file and use the
word find and replace command the export it back to Excel. This
assumes your cells do not have control characters such as Tabs and
Return/New Line characters in the text of cells.
(c) Use another application, such as a database or word processing
application. Excel is designed as a formula/spreadsheet calculator.
Your application sounds like you are using Excel in ways it was not
designed to be used.
(d) If you can, do something about the way your data is acquired,
before it gets into the Excel spreadsheet with all the errors you are
needing to correct.

Text cell contents can be up to 32,767 characters long. However,
formulas can only be up to 1024 characters long. The problem is that
while Find allows you to choose between searching values and formulas,
Replace assumes the formula.

I don't think huttite-ga's solution (a) will work. VBA basically has
the same limitations as the Excel interface:
 - The Replace method of the Range object also assumes you're looking
at the formula, and gives you an "Application-defined or
object-defined error" if you try it;
 - Using the VBA function Replace and setting the cell's Value
property truncates the string to the first 1024 characters.

Another line of approach would be to split the cells so that less text
is in each one. If you really don't want to do this, a macro could be
written to do it temporarily in order to make the changes and then
join it back again. I'd personally consider having them split
permanently, but that depends on the application.

Something that just occurred to me:

Probably the simplest way to do it is to simply copy the cells and
paste into Word, then do the find and replace there, copy them and
paste them back into Excel. This is similar to huttite-ga's suggestion
(b), except that it's much faster and easier and doesn't cause
problems with control characters in the cell contents.