Fix up encoding issues in ReplacementDict

One field in the replacement dicts can possibly contain non-Unicode values: originallocation. This causes an issue when interpolating in the value of the shared directory, which *is* a unistring (and could, theoretically, contain Unicode values).

This updates ReplacementDict.replace() to always use and return str objects instead of unistrings, to preserve all characters in both the original string and values in the dict and to avoid interpolating different string types.

This also updates the normalize.py client script and the transcoder to use ReplacementDict's methods, instead of its own implementations of them.