Distancie-se das funções "set locale" (como tsetlocale). Elas não têm a ver com o seu problema agora.
E o que nosso colega hugomg disse está certo. A saída do seu programa são bytes (tipo, são números). E como eles serão mostrados na tela de QUALQUER sistema operacional, depende do ambiente de execução do programa. Pra dar um exemplo, imagine um programa simples, que apenas escreve "Oi, mundo!" e termina. Se executarmos esse programa num terminal com codificação diferente do que os BYTES dessa string dentro programa têm, a frase vai aparecer de um jeito maluco. Se estiver certo, dá certo. Só isso.
Então, pesquisa um pouco sobre o seguinte (a Wikipédia é uma professora pra isso). 1) Codificação ASCII. 2) Codificação ISO-8859-1. 3) Codificação UTF-8. Lembrando que UTF-8 não tem mais correspondência de 1 byte por símbolo, como nas outras que citei.
Meus programas em C usam acentos nas strings dos printfs. E isso funciona bem, desde que as strings no código fonte tenham a mesma codificação do terminal/tela onde o programa será executado. Normalmente escolher a codificação comum do sistema alvo já garante isso. ISO-8859-1 e UTF-8 têm sido as melhores escolhas em 90% do casos. E os casos à parte ficam fáceis de mudar, quando precisa. Entende esse parágrafo?
Pra terminar, existe uma função e/ou uma biblioteca e/ou um programa chamados iconv. Com isso você pode converter suas strings de uma codificação para outra desejada. Pode ajudar também.
Resumindo:
descubra e escolha a codificação que todas as strings no seu código fonte têm; isso depende do seu editor, é simples.
Escolha a codificação que seu programa terá na saída, e isso passará a ser requisito pra quem for usá-lo; o termnal/tela da pessoa entenderá naturalmente as strings do seu programa. UTF-8 ou ISO-8859-1 são ótimas apostas, na minha opinião.
Por fim, você pode usar a função iconv() quando for necessário algo mais "detalhado".
Leituras úteis:
http://en.wikipedia.org/wiki/ISO_8859-1 (em inglês)
http://pt.wikipedia.org/wiki/ISO_8859-1 (em português, só pro básico; artigo não está tão completo, ainda)
http://man7.org/linux/man-pages/man3/iconv.3.html (manual da função iconv, em inglês)
http://www.gnu.org/software/libiconv/
http://en.wikipedia.org/wiki/Iconv