I have been getting the same exact message as well. I have had VM for 5 years and also own a HTC Evo 4g. I want to to know if your service has been restored or what anyone here has done to get it back.
I called Virgin tech support and they sent me a new phone....and it has the same problem! Help!!!!