Solução mais simples encontrada é adicionar essas duas linhas:
$str = str_replace('\u','u',$decoded);
$strJSON = preg_replace('/u([\da-fA-F]{4})/', '&#x\1;', $str);
Fique atento à sua versão PHP, pois uso 5.5 e nos testes não tive este problema! Meus testes deram assim:
echo json_encode($json, JSON_UNESCAPED_UNICODE);
[{"id":"1","nome":"Porto Alegre","estado":"RS"},{"id":"2","nome":"Rio de janeiro","estado":"RJ"},{"id":"3","nome":"São Paulo","estado":"SP"}]
echo json_encode($json);
[{"id":"1","nome":"Porto Alegre","estado":"RS"},{"id":"2","nome":"Rio de janeiro","estado":"RJ"},{"id":"3","nome":"S\u00e3o Paulo","estado":"SP"}]