I upgraded from 512/128 to 1500/256 at Netspace and their customer service says that the upgrade took place on 3 August. Upon checking the speed with the ozspeedtest.com tool at its Netspace mirror, I got what I did with the old connection. The modem is an Alcatel Speedtouch Home (rated to 8 Mbit/s) and there is a Netgear MR314 router in the network (which should not affect the WAN connection).
Solved!
All I had to do to solve this problem was to power down the modem and router and switch them on again. The new connection was at a higher speed (varies between 900 and 1000 Kbit/s).