The problem you're seeing is a bit of a quirk in Excel's data model features. Even after you delete tables and relationships, traces of them can remain behind as 'data connections', which can lead to lots of problems further down the line, as the old connections will not work properly if you try to use them.
You can find these connections by clicking Data > Connections > Connections. The simplest solution is often to remove all of the connections and start again, just to make sure that all of your connections are valid.
Hopefully Microsoft will fix this bug in a later version of Excel, but for the moment users should be very careful when creating data models. If you don't get it right the first time and try to delete and recreate what went wrong, it's likely that problems will occur due to Excel holding onto pieces of the original model.
I hope this helps and you're able to solve the problem, but if not please feel free to reply and I will take another look at it.
Jonathan is part of the professional team who answer Excel-related questions posted on the ExcelCentral.com forums.
Jonathan also tests our courses prior to publication and has worked on all of our ten world bestselling Excel books for Excel 2007, Excel 2010, Excel 2013, Excel 2016 for Windows and Excel 2016 for Apple Mac. Jonathan has also worked on over 850 video lessons for or video courses covering Excel 2007, Excel 2010 and Excel 2013.
As well as extensive Excel knowledge, Jonathan has worked in the IT world for over thirteen years as a programmer, database designer and analyst for some of the world's largest companies.