So interestingly, since my replacement ring this has stopped happening to me, its currently worked 100% of the time for the last few days.
I don't see how that could be but there it is. Maybe it is just because I removed all the old trusted devices and added new ones since the last phone update or maybe it the ring.
Maybe some of you guys could try removing all of your trusted devices and adding them again, see if that helps.
Since the last phone update...Whats your current android version?