Similar issue. I even emailed support on November 30th... they never even responded.
I found that often times, the Android app can discover the WeMo switches and plugs better than the iOS app. So usually when I get a new WeMo, I fire up an Android phone, connect, search, and then go back to my iPhone.
As for how my issue relates to the new Hub LR, when I first set it up, absolutely zero WeMo devices could be found. I was only able to find some of them by using an Android device to scan. Even then, it hasn't found all of them. There are still two -- a switch and a plug -- that it cannot and will not find, no matter what I do. I've reset the router, I've power cycled everything, doesn't matter. The new hub won't find it.
WeMo integration seems to be exceptionally poor now on the Flic platform compared to what it was two years ago, and Flic devs don't really seem interested in trying to fix it. I suspect it's because Belkin has changed things and are purposefully making it difficult for the devs. I know everyone's answer is "use IFTTT" -- and i would, if it weren't for the fact that IFTTT is painfully slow.