The trick for me (I have three of these) was holding the button down for about ten seconds, until you get a very long beep. Then let go.
Then pull out battery tray, remove batteries, insert batteries, push in tray while holding button down until hear one beep. Then a second beep will happen a few seconds later. Then start the connect new thing search.
Then they connected to my hub every time.