Unlocked iPhone 5 on Verizon
From the Apple web site:


  The unlocked iPhone includes all the features of iPhone but without a wireless contract commitment. You can activate and use iPhone on the supported GSM wireless network of your choice, such as AT&amp;T in the United States. The unlocked iPhone 4, iPhone 4S and iPhone 5 will not work with CDMA-based carriers such as Verizon Wireless or Sprint.


So the genius led you astray.