I have since upgraded to the S3 and I have not been able to get Wallet working yet on the S3. I keep getting the unsupported device error. I have tried a few different ROMs also and none have worked.
It's blocked on the Verizon Galaxy S3. You have to edit the build.prop file to "trick" it into thinking it's a device that's allowed. For me: I was able to change build.prop, install Google Wallet, set up cards, change build.prop back, and go on. After doing that everything seems to be working fine.
I think there's a thread over at xda with step by step directions for getting it up and running on a Verizon S3.