Yes I upgraded to the latest version at the same time as the server move. I have moved servers probably every 12 months always upgrade each time.
I still don't know what the root cause was but I have solved the symptoms with a DB query.
Viewing though the albums tab of the admin panel, all the albums and subalbums seemed to be published. However when I dug into the database I found the that they were not all published! A quick query on the db to directly update everything to published and everything is golden again
I can only assume some weird browser/cache bug was causing them to appear as published and thus the ensuing confusion!
So I guess that there are two take aways from this:
1. why did migration to new server / zen version lead to the vast majority of (previously published-state) albums becoming unpublished?
2. If what the browser is showing you does not ring true, then its probably not true and you should always get your hands dirty in the DB to check the 'facts'
Either way I am happy that the problem is solved, shortly before I post a new problem on RSS