Did a cold start with just the upstairs rads. One of the pipes at the top of the boiler went from luke warm to cold very quickly and the other one got very hot quite quickly. The pipes upstairs around the pump and valve got hot within a minute or so of the boiler firing up.
A couple of the rads got hot reasonably quickly but some of them took a long time to get warm and a couple stayed cold.
I think that confirms that it's a lack of flow problem - with the return pipe cold AND a good flow rate, the boiler shouldn't have been able to get the outlet hot all that quickly. Also, the pipes upstairs should have got hot quite quickly - tracking the rise in flow temp from the boiler.
I can't see it being a blockage since the system has been working for years. So either the pump is faulty, or the motorised valve isn't opening fully. The head should come off the valve, and you can manually turn the spindle - the flat tang is parallel to the hole or butterfly, so if it's parallel to the pipe then it's fully open.
After that, it's time to start taking bits apart unless someone has a better idea.