Well in theory, if you backup your iPhone in iTunes and then restore it to your new iPhone, it should transfer the data. I am going to experiment with it a little to see if that works. If it turns out that is not the case, I may have a way for you to save your characters independent of Apple. If you cannot get the data transferred, send me an email at
oubliette@gabysoft.com, and I will see what I can do.
In any case, you will not need to pay for the levels again. Apple will let you install the purchased content (except consumables such as portal gems) on more than one device. You simply purchase the levels/maps again, and you will get the message that you have already purchased it and asking of you want to download it again for free. I believe that there is a limit to how many devices you can put the game on, but I am not sure what that limit is.