If you don't have ArrayReplace then you probably have an old compiler. Are you running on Windows with BricxCC or on Linux or Mac OS X? If you are running on Windows have you updated to the latest test release from http://bricxcc.sourceforge.net/test_releases/
More importantly, you probably are not using the enhanced NBC/NXC firmware which is required if you want to be able to use arrays with more than one dimension. A string array is actually a two dimensional byte array. The standard LEGO firmware only supports arrays with one dimension - at least with respect to the REPLACE opcode which is what gets used when you try to change the value of an item in an array.
In any case, if you are using the enhanced NBC/NXC firmware then you will be able to use multi-dimensional arrays, including arrays of strings.
It is also possible that your code is having trouble due to some quirks with how NXC handles array declarations/initialization but that usually leads to runtime aborts rather than simply a value in an array not being replaced like it should have been.