I don't think bitcoins are illegal as such in Russia, as far as I've heard there exists some drafts, but they are not enabled yet.
I've heard that Iceland and Russia (and probably others) have laws in place regulating currency exchange and usage of foreign currency in the trade, and that both Russian and Iceland has defined bitcoin as a "foreign currency" in such respect. Such a classification may arguably be a good thing.