Then I came back to the car, pulled the handle, and got the "Tap Key..." screen. I held the door handle for probably 15 seconds, and then I heard the clunk and such of the car waking up. I reset and pulled the handle again and the door opened. No idea why it was so perfect one instance, and a few minutes later it was slow.
It could be the BT signal is transmitting from your phone but is blocked (BT is largely line of sight). If that's not it, your phones BT radio is probably not transmitting for whatever reason. While there is a small chance it's a hardware issue with your phone, this really sounds like a software issue, perhaps with another app on your phone that doesn't play nice with your phones BT. My wife and I have minimal other apps that use BT on our phones which probably explains our 100% functionality. Our phones do have whatever is necessary to use Samsung ear IconX (BT earphones) but we don't have other 3rd party apps that might not comply with Android BT.
I hope this helps other owners clean up their phones or do whatever it takes to get 100% BT functionality because it really is nice not to have to bother with a key fob or the card.