Don't you just love the Germans, they are a real stickler for rules and they take them to the absoloute maximum and love it. I have had my fair shair of small minded German beuracracy when I was working, they drive you mad.
A CE certificat is just a self certifications deceleration that the product meets all relevant regulations. There is no external testing that has to take place. A real UNO will have a CE mark on the back, mine has. A fake one or clone might not, it is probbly exactly the same thing and the far East people usually put on all sorts of marks that are not genuin. Most customs officers would not bother for a one off thing not for resale but you are in the one country in the world that would bother. I would ask them to send it back, at least in that way your sender knows you have not kept it and are demanding a refund.
Lesson learned, buy a genuin Arduino, and try and live in a proper country. ]