Error: Searching for Hue Bridge, Devices Not Available

Have you tried to only reset the hue bridge even though the hue app worked?
If not, try that next time.

I ones had a lost connection between homey and the hue bridge, after powering off and on the hue bridge it was fixed.