Maybe you didn't change the ID on the phone and/or the store?
1) On the phone, go to Settings - Store and find the line at the bottom that shows your Apple ID. If its the new one, don't do anything more with this step. If its the old one, press that line and then select "Sign Out." Then, press it again and sign in with the new ID.
Or, maybe...
2) At the bottom of a page in the App Store (I used Top 25 page), you'll see a line for your Apple ID. If its not your new one, then do the same as in above - sign out and then sign in with your new ID.
Of course, this assumes you changed your ID Via Apple's web site and not just created a new one. A new ID is not the same as changing the old one (and new IDs cannot be merged).
Hopefully, some of this helped. Do let us know how you get on.
Marilyn