I have exactly the same problem.
I updated my password via the My Virgin Media page -- and got the green box telling me that I had successfully updated my password -- but when I try to get to my mail is get the following message:
Your mailbox is not available at the moment.
Please retry again in one hour and make sure you are using the correct password to access your email from all of your devices.
I have tried multiple devices -- all reporting the same problem. Amy ideas?