Hi PayPal was frozen for me a few months ago – turned out it was a common issue and in the end I could not buy anything online or on console even though all methods valid and enough funds etc.
After contacting support here: support.xbox.com/.../contact-us
It turns out the issue relates to a risk block where by if you buy numerous items in a short time scale or have suddenly bought something after a long break then the system automatically lock your account to prevent fraud.
To remove the lock please contact support as above and explain the issue.
Be aware it took 5 days for a resolution for me but I have been told now up to 20 says so please be patient.