Existem duas coisas que podem ser afuniladas: CPU e largura de banda. O monitoramento da CPU deve ser simples e fácil de dizer quando atinge o limite. A largura de banda deve ser simples de monitorar, mas é mais difícil saber quando atinge o limite, já que o EC2 não garante uma certa quantidade de largura de banda de rede. Você poderia fazer alguns testes de largura de banda e deduzir um limite disso.
Em qualquer caso, os problemas de rede serão mostrados nos clientes na forma de retransmissões TCP. Monitorar isso em todos os clientes irá informá-lo quando houver um problema, mas não necessariamente se é com sua instância NAT ou qualquer outra coisa.