They may or may not, be trying to scam you.
Best to play/stay safe, and assume, they might be. So, best to stay within the paypal/ebay system, to protect your money.
Which is what other(s), seem to be recommending in this thread.
Another way of looking at it, is that ebay has been running for an extremely long period of time. So, why has someone just started up a new selling account ?
There is a serious risk, that they have scammed people in the past, and/or are trying to hide the big negative feedback, they have accumulated on their previous ebay accounts.
The fact you have paid the money to paypal, and they claim to have not received it. Already sounds very fishy/suspicious to me.
My guess would be there is at least some element of a scam going on.
Paying another way, is a very bad idea.