to comply with the energy efficiency regs and probably building regs when they installed your new boiler they should have also upgraded your cylinder to one with the latest high heat recovery coil, as well as fit thermostatic radiator valves to all but one radiator and i think the pipework from the boiler to the cylinder is also meant to be fully lagged to comply. this extra requirement and expense is why most installers and householders go for a combi replacement instead of a traditional boiler/cylinder/tanks system.
thinking logically i would doubt the problem is to do with scale if the hot waer was working fine with the old boiler a day or two before the new boiler was fitted and now it isn't .
i'm not brilliant on the old systems so cant really suggest anymore, you need to ask gasman but to get him to answer you will probably need to repost this questio in the main home and garden section.