Old Apple ID's don't work
When you say they "don't work" where exactly is this happening? Have you tried logging in directly via the apple website? Eg, (I forget the precise url, but) if you try http://cloud.me are you able to login with your old credentials there? 

Have you tried via alternative mediums: iTunes directly (ie not via the phone)

And are you sure it's not an authorisation issue in that you have too many authorised computers/devices

Finally what happens if you try "forgotten password" on the website, does it say the old accounts are invalid?