This is not the whole story. ReplaceAll (and related functions) use the FullForm for pattern matching, and to replace a part of the complex number one needs to use this form. It is true that 3 + 4 I is atomic but one may use the head of this expression to get into its parts
Your thinking that I is reserved is correct, but that isn’t sufficient to override the principle that anything beginning with a letter followed by any number of letters and digits will be considered to be one symbol. This kind of problem shows up again and again and again and again…
Without any disrespect, whats the fuzz? The OP’s replacements does seem to work (provided there is a space left between I and the variable symbol):
In[1]:= test = {{a + I b, b + I c}, {d + I e, e + I f}}
Out[1]= {{a + I b, b + I c}, {d + I e, e + I f}}
In[2]:= test /. {e -> 1, f -> 2}
Out[2]= {{a + I b, b + I c}, {I + d, 1 + 2 I}}