I contacted Garmin support, and they asked for Galaxy S5 phone information and screenshots of the failed pairing/connecting process.
They also asked for the Garmin Android sync log, but my logs were empty because I removed and replaced the app thinking that would solve the issue. Of course, it didn't.
I wonder if there's a way to roll back the Verizon update? That should be an option for resolving this issue.