It is turned out that "publish_checkins" permission is not supported now. I wasn't even able to add this permission at Facebook application configuration page (App Settings -> Permissions)
Now I post to timeline with place id and it works just fine (you have to ask for "publish_stream" instead of "publish_checkins" permission).
Thanks!