Same thing happens to me. I really believe it's some sort of deficiency or timeout on the PayPal sandbox site. The thing is slow as molasses, and it wouldn't surprise me if they time out on the response after registering the payment, sending back the internal service error. It's the nature of the beast... I wouldn't sweat it too much. Let me know if it doesn't work in production.