EC2 server can't resolve hostnames

When trying to resolve a hostname (i.e. using dig), the server almost always fails, saying ;; connection timed out; no servers could be reached. Around one in ten attempts works, usually after a long waiting time.

Strange thing is that the same behavior happens also if I'm querying a different DNS server (Google's).

My default nameserver is Amazon's, @ 172.31.0.2 . I get this one automatically when the server connects using DHCP.

Pinging the IPs (8.8.8.8 & 172.31.0.2) also usually fails.

I've tried checking the VPC settings and security group settings, but found nothing. Also the fact it works every once in a while makes me even more confused.