I personally spent an hour on the phone with RIM to resolve this problem:
First, I had AT&T reprovision my phone - checked all OK
Then, with RIM Tech Support on the phone and one of my contacts in the UK available,
Sent PIN request via contact list - OK (checkmark with D on my phone)
PIN request via contact list received in UK - OK (verified contact received)
PIN accept sent from UK to US - fail (lays pending checkmark no D or R)
Sent direct PIN request to UK - OK (checkmark with D on my phone)
PIN request recieved in UK - OK (verified contact received)
PIN accept sent from UK to US - fail (checkmark but no D or R)
So now RIM knew that the problem was on the return trip from the UK computers.
RIM asks my UK contact to continue trying a direct PIN request from UK to US intermittantly during the next 48 hours.
Within one hour, the pipeline between the US and UK was open and I was receiving PIN requests and was able to answer and communicate via BlackBerry Messenger once again no problems no lag time.
Evidently there was an equipment upgrade and the handshake configuration was incorrect.
This procedure opened communications for N America and the United Kingdom at approx 4:00pm EST.
So, if anyone is still having problems connecting overseas via BBM, call RIM Tech Support (1-877-255-2377 from the US) and have an overseas contact available to help with realtime diagnosis and reporting.
Hope this helps.