Trademark, copyright, patents
"Surely to trademark something you have to actually prove that you own it in some way - Either you developed it yourself or you paid someone to develop it for your company?"
Nope. Trademark is not a patent, it is just claiming use of a particular logo or symbol for your particular line of business (plus trying to deny use of "confusingly similar" logos and names.)
"I thought you couldn't trademark something that is in common use within a certain context. The smilie already existed, so he can't copyright it."
That's right, except they were claiming trademark, not copyright. And apparently, per a few posts above (the post by Christoph), the Russian trademark agency agreed, the trademark was denied.
To avoid confusion...
Patents cover inventions*, trademark covers logos and names, and copyright covers copying creative products**. Coca Cola for instance -- if I tried to clone Coca Cola, if the formula is patented they could try suing for patent infringement if my copy was close enough (really they couldn't, any patent would have expired over 75 years ago, but...) If I called mine Coca Cola, they could get me for trademark infringement, or if I used like a similar logo but called it Coka Cola or something. It's supposed to be based on the logo or name being similar enough to cause confusion. Copyright? Wouldn't apply as much (since it's more for books, music, movies, software, etc.), but if I copied the non-logo graphics for my bottles, they wouldn't be covered by trademark but would be copyrighted.
*Patents cover inventions, plus whatever other crap the local patent office allows people to slip by... in the US for instance, they allow software patents (ugh), they allowed business method patents until recently (ugh!!), and I think may still allow genetic patents (ughhhh!!!!!).
**Creative products -- so copyright isn't supposed to apply to just data collections. But, despite this there've been copyright cases here in the US about copying data (in bulk) from phone books and Westlaw, they do both assert copyright even though by strict interpretation it's just a collection of phone numbers and legal cases. It's legally clear cut, but in actual cases, they'll be like "collecting all that info is a lot of work", and some judges (contrary to the letter of the law) decide it's copyrighted.