Ive been on contact with hostgator and they cannot find anything wrong at their end. They requested a tracert which I promptly gave them and they have come back to me saying the following:
I attempted to do a traceroute back to your IP address and we seem to be having almost 100% packet loss on this hop : mdr-fid-int.akbr5.global-gateway.net.nz
The registrant contact name is being listed as: Telecom IP Limited
Im not too sure where to go from here to see if I can get it resolved. Its refinately a recent thing as opposed to a long, ongoing thing. I really started noticing it around 10 days ago.