É difícil dar respostas específicas, já que 90% desse trabalho é experiência que ensina onde procurar o tipo de problema, e os outros 90% sabem onde procurar no Google para obter dicas de por onde começar.
Eu geralmente tento o material da sacola de papel como fazer com que o cliente demonstre o problema (principalmente para descartar problemas com os dedos e quaisquer problemas que o cliente possa ter descrevendo seu problema) e tentar duplicar o problema em outro computador. Isso faz com que você saiba onde procurar.
Não esqueça o problema corretivo de uma reinicialização, especialmente para sistemas Windows, até hoje. Costumava ser assim tanto que eu perguntava às pessoas "Você reiniciou? Bem, tente isso e deixe-me saber se o problema persistir" - isso corrigiu uma grande porcentagem dos problemas que me foram perguntados.
Frequentemente, há problemas pendentes em problemas de resolução de DNS e conectividade básica (ACLs em roteadores, lacunas de ar na rede, pings / traceroutes / mtrs em sites remotos, etc.).
Para serviços sobre os quais você tem controle direto, a execução de nagios ou algo para garantir que o serviço esteja realmente em execução pode, com frequência, levá-lo a corrigir problemas antes que os clientes os informem sobre eles. Você provavelmente também quer estar executando a coleta de estatísticas, seja diretamente através do munin ou algo assim, ou via SNMP para algo como o Cacti.
Eu costumo tentar ter o Cacti rodando contra pelo menos todos os meus principais switches e firewalls; sempre que possível, corro o Cacti contra tudo o que posso. Nesses casos, geralmente estou procurando itens como contagens de erros de porta ou tráfego excessivo. Os gráficos de firewall de alguns dispositivos podem mostrar o uso da CPU e as sessões simultâneas; você aprenderá em quais limites seu dispositivo de firewall começa a ter problemas.
Seu firewall pode logar em um dispositivo syslog; se assim for, registre tudo que puder e procure por sugestões. Isso será mais fácil se você executar algo como syslog-ng ou rsyslog ou splunk que permita dividir seus logs um pouco, em vez de lidar com um arquivo monolítico.
Eu também tento rodar o nfsen pelo menos dentro do meu firewall, e o uplink para o provedor de internet onde for possível. Isso permite que você volte no tempo para ver as sessões e ver quem estava fazendo o quê; isso às vezes pode pegar comportamentos interessantes.