just to get a dialog started,
are you ABLE to AT LEAST get on crackbook and youtube? Can you at least access the sites?
and if you can, no matter what video you choose, you get this error but only on the cellular network?
are you sure you are no roaming on verizon when this occurs? what is your signal strength when on the sprint network when this error occurs?
have you done a profile and PRL update?
soft reset the device?
you are not rooted are you?