Stuck - Thanks Apple!
So I took the plunge and tried updating my iPhone 4 to iOS 5. I marvelled at the shiny new process which allows untethered activation.
I then got frustrated when presented with the following message:
But wait! It says on the screen that I can connect the iPhone to iTunes to activate it the old-fashioned way. Salvation!
Thankfully I got it resolved by borrowing an unlocked SIM card - once inserted into the iPhone the activation server started working again. I can’t tell if it was the unlocked SIM or a coincidental re-appearance of the activation server which did the trick.