Open a paypal dispute straight away and correspond with the seller through that, repeat anything you have already said to them so there is a record.
If you don't get anywhere, escalate the dispute to a claim for bad packaging and poor grading. Paypal may ask you to get a recognised record dealer to examine packaging and record and back up your claim.
If paypal find in your favour, you will then have to return the record, using a tracked postal service. When the tracking shows the record delivered you get your refund.
Don't worry about the neg feedback, you can leave it once you have escalated to a claim if you want, but unless the guy has loads it has very little effect and he'll just start trying to get it removed and use it as evidence of a stroppy buyer in the claim process.
Its a pain in the *rse but it does work.
Cheers
Paul