Are you sure you uploaded all of the files from your localhost? The ones on your server wouldn't work from anywhere.
Upload: checkout.php, confirm.php, confirm_cart.php, and pp_confirm.php
If it works on your localhost, maybe you just didn't upload the latest version of the files. The files on your live server would not work on localhost either.
There seems to have been an issue when running the checkout wizard. The store to database code is not on the page correctly. Please try running the wizard again to regenerate the pages.
There seems to be an issue with the paypal sandbox environment right now. They may be working on it.
I'd suggest using a live account for testing for now rather than sandbox. Just do small dollar amount transactions and refund them after you are done testing. Paypal refunds all fees associated with a transaction, so there is no real risk in doing it this way and you can get around the sandbox inconsistencies you are experiencing.