The NBN isn't replacing all of the internet infrastructure in Australia; it's only responsible for part of the chain that your data travels along.
Your setup: Within your home or business, there are several factors that can affect your internet speed such as your router, the quality of your hardware (laptops, phones, etc.), how many devices you have on your home network and the internal wiring of your premises.
The consumer access network (CAN): This is what NBN is replacing with its mixed technology model. The CAN is all the fibre optic and copper cabling between your house and the point of interconnect (POI). The POI is where a telco provider network connects to the NBN. In the case of ADSL, the CAN was all the copper between your house and the Telstra exchange building.
The NBN transit network: The transit network is made up of thick fibre optic cables connecting all the POIs together. NBN is also responsible for this.
Telco provider networks: After the POI, NBN has no control over your data connection. This part of the broadband network is owned and operated by service providers such as Telstra, Optus and TPG. Whenever you do anything on the internet, the signal has to travel through your service provider's data centre or centres. If this part of the network is congested or faulty, your connection will be affected just the same as if NBN's network was acting up. Smaller providers who don't have their own telco network not only have to purchase capacity on the NBN, they also have to pay larger providers for "backhaul" on their networks.
International connections: If you're visiting a website or using a service that's hosted overseas, any part of the data journey between your house and another country can affect your connection, including the telco or national broadband networks of that country.