Replaced replace-key with replace-keys, which takes a map of
old-key->new-key. Still having a "Key missing from internal nodes"
error, but luckily it is always happening on the same key, even though
I'm now using a hash-map to insert instead of a sorted-map, so at
least it's reproducable.