Hmmm... I see no mention of Verizon blocking the app anywhere on this page, just Sprint and AT&T.
Don't have any other smartphones near me atm, when I go to work tomorrow will grab a couple peoples other devices and see if it is being blocked in the Play Store, should be able to get my hands on a few Motorolas, Samsungs, and maybe even an LG and let you know.
EDIT: BTW, when I go online it still shows compatibility with my VZW Samsung Stratosphere (SCH-I405) also a 4G device, just not my Rezound. So if VZW is blocking it, they are being device specific.