The nautilus extension doesn't create a login shell for remote connections.
When right-clicking a remote sftp folder in nautilus then choosing "Open in Remote Terminal", the shell opened isn't a login shell. This is the case with either bash or zsh on the remote machine (I haven't tried other shells).
In my case this caused locale issues on the remote shell (all set to POSIX instead of configured locale).
I tried guessing the command executed and it comes out to something like
ssh -t user@host -p 22 cd /path/ && exec $SHELL -.
Changing it to
ssh -t user@host -p 22 cd /path/ && exec $SHELL -l worked (tested with gnome-terminal's
-e option, I didn't recompile gnome-terminal).