The problem is that for function templates, the template parameters are deduced by the compiler based on the types you are passing in as parameters. The replace function is really a template function. It looks like:
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
So if you pass in iterator, iterator, int, char, it looks for the prototype
void replace(iterator, iterator, int, char)
Since the last two parameters are always the same type, the compiler can't find it, and it barks at you.
If you are going to be using characters outside the ASCII and extended ASCII set (i.e. characters that require more than 8 bits), you should probably consider using wstring instead of string. However, the global streams cin, cout, and cerr used for console input, output, and error are only capable of handling char data-- not wchar_t data.
Here is my previous example, tweaked to use a wstring instead of a string. This uses the *NIX device /dev/tty to write to the console, since I can't send a wide-character string to a cout (a character stream).
wstring s(L"Hejjo Worjd!");
replace(s.begin(), s.end(), L'j', L'l');
// Create a wide-character output stream to write to the console.
wcout << s << L'\n';