Mine works on att. However I had the same issue. Unfortunately I was doing my phone setup very quickly. I believe what finally worked was an update to Pay from the play store. Sorry I don't recall for sure.
Same results after Factory Reset. I've tried uninstalling the Samsung Pay updates and reinstalled and same result. I might have to return the phone for another.
Could be a Samsung Pay issue with the Imei since the Imei us tied in with the security. You can call Samsung and talk to the Pay division who will help with that. Happened to me when I switched out phones because of a replacement. Samsung took the new Imei and other info and Pay was working again.