I would try again in the Add/Edit pages to move the page down and then back up again a few times, ie move the one that is not supposed to be the home page down and move the one that is supposed to be down and then back up to the top. The only thing that makes a home page the home page is that it is a root level page (ie with no parent) and it has the lowest sort order of all the root level pages.
I would also go into the page settings of the pages that were child pages of the deleted home page and make them child pages of the new one. When the old home page was deleted that kind of orphaned the child pages to become root level pages so they have a sort order that may conflict with other root level pages because their sort order was created based on their old position below the old home page, by moving them back where they belong it may help.
Hope that helps,