I had the same problem with iMessage when I switched over. As mentioned, make sure your phone number is unckecked/removed from ALL Apple devices (my Mac was the final culprit causing problems--Daveathall's post is spot on for fixing that).
Also, switching over at AT&T was unnecessary--could've just moves the SIM card over. I did that with my iPhone 5 using an adapter and just had to manually update the APN settings and was all set. Did the same thing again with my Note 2.
Best of luck with the Nexus, definitely a great looking phone.
Thanks. I'm talking to my friend right now and she's saying that my number isn't showing up as iMessage compatible anymore, so it looks like it just took a really long time to update in the iCloud servers.