If you read through this sorry saga you will find details on how to do the necessary Trace Routes and then PINGs. If it is the same problem as ours this will speed it up.
As for changing the DNS Servers: let me know the result of above as if this 'fixes' it there will be no need to change them