nb_NO.UTF-8 de fato não existia. Mudando para no_NO.UTF-8 resolveu o problema. Na verdade, o problema foi introduzido por LANG = C, que foi definido por algum outro motivo. Remover isso faz com que o OS X defina LC_CTYPE = UTF-8 por padrão, o que funciona fora da caixa.