News app stopped updating

Hi all!
iOS 9.1, iPhone 5s. Native News app stopped updating some of my feeds, I deleted all of them and tried to add them again, but search became unavailable. iOS 9.2 did not solve this problem.
Has anyone encountered that?
Thanks, Felix