Similar problem when connecting via SSH to a remote sever (after having installed oh-my-zsh on my local, but I'm not sure that's relevant). To fix it,

On my local machine, I edited the /etc/ssh/ssh_config file, commenting the SendEnv line

#SendEnv LANG LC_* 

Tab completion now works without the warning on the remote machine

bash: warning: setlocale: LC_CTYPE: cannot change locale

I had a similar problem when connecting via SSH to a remote server (after having installed oh-my-zsh on my local, but I'm not sure that's relevant). 

To fix it, on my local machine, I edited the /etc/ssh/ssh_config file, commenting out the SendEnv line.

#SendEnv LANG LC_* 

Tab completion now works without the warning on the remote machine.

bash: warning: setlocale: LC_CTYPE: cannot change locale