There is some logic for Apple to release the iPhone to the largest of the 3 remaining carriers first. Then slowly release it to T-Mobile and Sprint after a few months so that each of the networks can handle it.
I think it'll be in the summer when the new iPhone is released. They said it was a multi year non exclusive deal, but I believe verizon paid extra to get the iPhone 4 now instead of waiting for the iPhone 5 this summer which I believe will be both CDMA and gsm, and will be released on all carriers.