We apparently jumped the gun just now and reported everything as OK.
We had connectivity across all hosts / our entire ip range for about 2-3 minutes and then everything went down again.
This really indicates that the automatic blocking which they have been fighting in the datacenter all night is being triggered again.
I guess we will have to be patient a little longer - although it's promising that we saw things working, albeit briefly.!