Oooops, sorry cavein, I mixed you up with merriman_uk!
Keranu -- immediately take steps via ebay AND paypal. At the very least, write a short letter documenting what happened (i.e. the seller is advertising a genuine product but actually selling a bootleg) and how this matter can be resolved (i.e. you want to cancel the transaction immediately and get a full refund). Tell them you can provide more details, but keep your first letter short and to the point.
Make sure you keep a record of all your emails, since you will appear trustworthy when you can provide documentation to support your claims. Save all of your correspondence with the seller, paypal, ebay.
This is the minimum you should do, I'd try to stop payment (if possible) ASAP
merriman_uk -- Do the same thing as Keranu. If you didn't use paypal, take the appropriate steps (perhaps we can help?). For example, if you sent the equivalent of cash (money transfer, money order), I don't know if you have any recourse outside of ebay. In the US, money orders from the US Post Office do have some guarantees, but I'm not entirely clear on the details. That's the sort of thing that you'd have to figure out, since you are on the other side of the pond.