I beleive the F&R should work for the Selected region/Column only in 2003 as well.
If its the single column values that you want to replace, and if F&R is working for the whole sheet. Try copying the column to a new sheet, DO the F&R and Paste it back to original sheet.