Any time I start Voice Chat I get "Video Chat Service Error", and it's been that way for at least 4 days, perhaps as many as 6... anyone else? Very annoying, especially that it wouldn't be fixed by now.
Happened to me this morning, a restart cleared it all up. Since you said it has been happening to you for about a week (assuming you do shut it down as opposed to standby) I would suggest a hard reset by pressing (vol+ and vol- and power button) at the same time until it resets. Good Luck!