Issue

Consider the internal structure of a SparseArray object. For example:

s = SparseArray[{1, 0, 1, 0}]; s //InputForm 

SparseArray[Automatic, {4}, 0, {1, {{0, 2}, {{1}, {3}}}, {1, 1}}]

Clearly doing something like:

s /. 1 -> 3 

should not convert the SparseArray object into:

SparseArray[Automatic, {4}, 0, {3, {{0, 2}, {{3}, {3}}}, {3, 3}}] 

which is not even a valid SparseArray object. Instead, it needs to do a replacement on the equivalent Normal version. Getting this to work right is not easy, which is most likely why it doesn't work. There is too much variety in the patterns and levels that can be used in a replacement.

That doesn't mean that the only way to do a replacement on a SparseArray is to use Normal or ArrayRules and then convert back, though. Assuming you just want to apply a replacement rule on the elements of a SparseArray object, here are two possibilities.

SparseArray iterator

If you have a 1-D vector sparse array, you could use a SparseArray iterator. For example, here is a function that uses a SparseArray iterator to do replacements of a vector SparseArray:

VectorReplaceElement[s_SparseArray, rule_] := Table[Replace[i, rule], {i, s}] 

The key here is that rule is applied to each element of the SparseArray, that is, the level of the replacement is constrained. Applying this function to my initial example:

r = VectorReplaceElement[s, 1 -> 3]; r //OutputForm % //Normal 

SparseArray[<2>, {4}]

{3, 0, 3, 0}

We see that the replacement has happened as desired. Note that the speed depends on the number of nonzero elements in the SparseArray. For example:

s = SparseArray[Thread[2^Range[40]->1]]; s //OutputForm 

SparseArray[<40>, {1099511627776}]

It would require a computer with many TB of memory to be able to convert this SparseArray to a normal matrix.

new = VectorReplaceElement[s, 1->3]; //MaxMemoryUsed //AbsoluteTiming new["NonzeroValues"] 

{0.000049, 2360}

{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

Clearly the replacement worked, and the SparseArray was not converted to a normal matrix in order to do the replacement. This method doesn't work as well for higher rank SparseArray objects.

Structural replacement

The other possibility is to extract the nonzero elements, and the default element, apply the replacement rule, and then reconstruct the SparseArray. Here is a function to do this:

ReplaceElement[s_SparseArray, rule_] := With[ { elem = Replace[s["NonzeroValues"], rule, {1}], def = Replace[s["Background"], rule] }, Replace[ s, Verbatim[SparseArray][a__, _, {b__, _}] :> SparseArray[a, def, {b, elem}] ] ] 

Again, this approach does not convert the SparseArray to a normal matrix:

new = ReplaceElement[s, 1->3]; //MaxMemoryUsed //AbsoluteTiming new //OutputForm new["NonzeroValues"] 

{0.000065, 3864}

SparseArray[<40>, {1099511627776}]

{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

And it works fine with higher rank SparseArray objects:

s = RandomInteger[1, {10, 10}] //SparseArray; new = ReplaceElement[s, 1->10]; new //OutputForm new["NonzeroValues"] 

SparseArray[<54>, {10, 10}]

{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}