Why can't I sign up for Android Pay?

[AC Question]

I am currently on a Nexus 6, Verizon, updated to the most recent version and build (6.0 build MRA58R). I used to be rooted prior to Marshmallow, but unrooted my phone completely and updated. I am trying to use Android Pay to add my credit cards, but it always gives me the following error:

"Google is unable to verify that your device or the software running on it is Android compatible."

Why am I getting this error and how do I fix it?

 

[dpham00]

I would try to reflash the stock image

 

[AlphaTango414]

+1 on trying a fresh firmware flash to your device. If problem persist, try contacting Google support for Android Pay.