2010 Find/Replace on Formatted cell

So I need to mark all cells in my sheet that have a Red background with an 'X'.

I use Ctrl+F, choose replace, and under the Format button I select 'Choose Format From Cell'

Works fine if I select a cell that I set the background myself.

I have a sheet from a client where this process does not work at all.

I can copy a single cell from the original, put it on a brand new sheet in a brand new workbook, and it still won't work.

I get the following error:

"Microsoft Excel cannot find any data to replace. Check if your search formatting and criteria are defined correctly. If you are sure that matching data exists in this workbook, it may be on a protected sheet. Excel cannot replace data on a protected worksheet"

Please help before I smash my machine.


Excel 2010, Window 7, if it matters