Yup, trying to solve my own question (again):
Similar problem here:
http://drupal.org/node/1115978
and the possible solution here:
http://drupal.org/node/1023190
Update
The above solution was about a database fix to do with feeds that have more than one category.
When I applied to patch I was informed that this was already in the version of aggregator.
So in summary the solution I gave above had already been applied.
However, another avenue to explore is cron job time out. In my situation I have a lot of feeds so it could be taking the job invoked by the cron a long time to update all of them.
Here is another possible solution to extend the time alloted to running a job triggered by cron, a cron job:
http://teqsnacks.com/2007/07/07/drupal-when-cron-jobs-do-not-complete-and-cron-jobs-tips/
To quote:
Go to your settings.php
file (under sites/default or wherever it
is). At the bottom of it you will see a list of ini_set commands. Add
the following to the list:
ini_set("max_execution_time", 60);
The number at the end is the number of seconds a program can run
before timing out. Setting it to 0 means "never timeout" which you
should use very carefully, like on a development site where you have
control over the server.
Update 2 - and likely solution and root cause
The cause of the problem likely stems from a corrupt database causing errors when the cron job is run. Details and remedy here:
http://drupal.org/node/1596220
Update 3
After following the above instructions you may still see the feeds not updating. Further things to consider:
Clear all caches
Check your site logs for cron job running successfully and new feed items being imported from the aggregator
If you are using a View (of type aggregator) to process the feed then you would probably need to sort the feed by descending so that the latest feed items appear first. To do this you will need to define your own date format (check the PHP option) for the Aggregator Feed Item Timestamp in the View sort criteria, so that the date is big endian i.e. YYYY-MM-DD hh:mm:ss. The current date formats offered aren't purely big endian and the sort won't work properly e.g. because day comes before month.