What kind of phone is it that you had before? That typically doesn't happen going from iPhone (3g or greater) to an android handset. I move back and forth between iP4 and Atrix with no problem. Qualifier for those who will digress: I did get a text from att the first time I went to a 4g phone saying that I needed to call them, but it was just a feature code they added on to my account.
If you went from a blackberry or OG iPhone, then yes you will need to call and change plans. Blackberry plans are not compatible with iPhone plans and vice versa.