Request not validated means that PayPal didn't know of the details you sent through to it. Are you generating requests from the sandbox, using users that you created in it?
I haven't done anything with the sandbox since writing the initial code, but I did have it working then. If it doesn't work now, then maybe something has changed, but using the live PayPal site does work.