It was a very slow and frustrating start, but I gave myself one week to do deliberate practice every day for at least 15 minutes and then to see if I'll go back to qwerty.
I forced myself to use Colemak even when replying to instant messages, which raised couple of reactions when there was "X is typing..." for several minutes just to see a short reply :)
I also found a Colemak keyboard for my phone, so I had Colemak on all my devices. I found this to be really helpful.
----
That one week has passed, my speed and accuracy got better. I started to appreciate the layout more and more.
Now I have the same speed I had with qwerty, and I like typing with less movement of my hands. Many typical shortcuts stayed in the same place (not Vim's HJKL, unfortunately), which is a plus.
Cons of using Colemak? Now I can't type on other people's qwertys ;)