AT&T's network uses GSM tech while Verizon's network uses CDMA tech. They are not compatible with each other. For example, Apple does not simple make a single version of the iPhone 4 for AT&T and Verizon. They make one version with GSM circuitry for AT&T and they make another version with CDMA circuitry for Verizon.
that and CDMA phones through verizon have no sim card slot (unless you buy a global ready phone)
if you had a warranty on your phone perhaps you can get a replacement. if not perhaps they will work a deal out with you in exchange for a contract renewal (doubtful). you will probably end up buying a new phone unless someone has an old verizon phone laying around that they will give to you.