Can you verify the dns servers of your new ISP? Usually you can log into the router and see what it has, if you have one. also, you can do an nslookup of google.com or whatever, and the first lines will be the DNS server your machine queried. If it looks like it is still using your old DNS, then flushing did not work as planned.