This new online-only CompUSA has been trying to shaft people left and right over things like this. You shouldn't have to pay $60 to get your faulty item replaced.

So you need to press them on it. Demand an exchange. Get mad. Demand to speak to a manager. Most importantly, explain to them that it shouldn't matter how you paid for the device: you ship them the faulty unit and they ship you a new one, case closed. Paypal or credit doesn't enter into it. It sounds like they're just making excuses to make you either give up or pay for the more expensive item. It doesn't matter how inconvenient it is for them, they sold you a faulty product and you're entitled to an exchange if it's within their replacement timeframe.

Failing that, you should have a 1-year warranty from Nokia. Check their website or the warranty booklet that came with your N810.