AT&T iPhone back up to Verizon iPhone?

I recently purchased a verizon iPhone. I originally had the AT&T one. I want to transfer all my contacts, apps, photos, and such over so I created a back up. I know, I can transfer contacts over using the back up assistant, but I want it to look just as my last phone did, backgrounds and all. Unfortunately, When I plug in my new phone, that newly created back up is unavailable! I looked and I DID make it. It's under preferences and devices, so the back up was made. I can even restore my OLD phone using it. Why can't i use it? And If there's a way to, how?
Okay, so obviously the phones have different serials and I assume that's the problem? Is there a way around this?