"or perhaps take a look at our store to see what the issue is?"
The issue is with using Paypal standard as the gateway, really. this is why i asked about which gateway you are using.
the comprehensive answer is to change the gateway to Paypal Express checkout instead of using PayPal payments standard.
Express checkout is the same user experience and is also a free service from PayPal.