I also received this error on testing Payments Pro in the sandbox. I sent a message to their support and got the following back:
Internal Service Error is usually caused by using a credit card number
like 41111111111111111 etc, which has been used so many times in the
past in Sandbox environment. I would advise you to try one of the Visa
card numbers below:
I had used the 41111111111111111 Visa test card (PayPal's published list of test cards here - http://www.paypalobjects.com/en_US/vhelp/paypalmanager_help/credit_card_numbers.htm). Presumably they could see I'd tried to use that card number from looking through their logs.
Anyhow, in my situation, using the above numbers worked fine for me - with no other changes in Magento or in my PayPal account.