It turns out our IP Addresses are both in the range 218.101.50.*. We have tried everything and have become convinced the problem is with telstra and their network.
Of course telstra deny this (maybe rightly so, or maybe not).
So.... are there any other users out there in this IP range, who successsfully use a router directly? Or other users with the same issue?