Whilst trying to pay someone I encountered a problem on paypal.
I had copy and pasted his email into the box where you enter the person you are payings email address. This then came up with an error, something along the lines of:
Please enter a valid email domain address
Couldn't get my head round it until I manually entered the address.
Joy it worked!
So, if you have any problems try this as I think they may have been messing around with their security settings.