Did you install the very last version of TO (version 6.0 build 544)?
Did you make sure the object is of the same 'Kind' as the one to be replaced? If not then it won't work.
Finally, I still sometimes find that a replacement doesn't work, or to be more accurate, after listing all the assets in a map, right-clicking on one asset does not bring up the menu with the required F7/F8 replacement option.
In these cases, I close and re-launch TO, and make sure I display "ALL" custom objects before analysing a map and attempting a replacement.
If all that fails, I don't know what the solution could be.
~ D