There's a lot of problems with the 5.0.1. I have Bluetooth problems, battery problems. and several others. I had a Note 4 with Verizon before I went to Sprint where I also had a Note 4 and now I'm back with Verizon with the Note 4 again. I know it's not the phone or how i use it since i don't leave location on or other battery draining settings.
Republic wireless knew about the problems with lollipop and went straight to Android 6.1...
The Note 4 on Verizon received 5.1.1 on January 11th. Check for software updates. Also, as a note, Android 6.1 isn't fully released yet as not even the Nexus devices have it. 6.0.1 with the January Security roll-up came out last week. Samsung isn't slated to begin Marshmallow roll-outs until Q1/Q2 for their phones. Carrier-branded phones will likely take a little bit of time beyond Samsung's initial launch to get the update.
I have 5.1.1 on my galaxy s6 (not sure when I got it) and am still having bluetooth connection issues in my car. Constant connect and reconnect it's awful.