Bluetooth Issues Fixed by Verizon Re-Synching Phone

I've been having some BT issues after the Lollipop update, so I went into my local Verizon store to see what's going on. They called technical support for me and a very nice lady called me on my phone and we went through a bunch of different things (turning BT on/off, Wi-fi, Network, etc.) even sent texts back and forth with images to see if I was receiving them.

She told me my phone was "out of sync" with their towers so she re-synced the phone. This seems to have improved my BT issues. I thought I would post about this here just in case anyone else wanted to contact Verizon and see if their phone is "out of sync". Worth a try if you've tried everything else.