Deleted link to deleted page- its still going to deleted page

I updated a page and then clicked SAVE AS and gave it a new name. I then deleted the old page. On a separate page I deleted the LINK to the old page and created a new link to the newly created/Saved As page. The new link keeps opening to the deleted page. I have removed the old link and re-added it repeatedly, saved the paged and published repeatedly. Its not updating.