A mensagem é bem clara:

• você entrou em contato com um banco de dados
• as credenciais fornecidas estão erradas

Isso indica que não há realmente nada de errado com a configuração do seu cliente.

Então, isso deixa você com

• a combinação usuário/pw está errada
• você não entrou em contato com o banco de dados que acredita ter

Possibilidades:

• Certifique-se de que você pode se conectar com as credenciais fornecidas na linha de comando.
• Use tnsping mydatabase para verificar o host e a instância que você está entrando em contato, verifique se está correto. A saída desse comando deve informar o host, a porta e a instância/serviço aos quais você está se conectando. Se estiver errado, verifique o arquivo tnsnames.ora para este alias.
• Como sugere @OMG Ponies, se você estiver usando 11g, verifique se as maiúsculas e minúsculas em suas senhas estão corretas